FishMarket 1.0/FishMarket v1.0.iso/fishies/126-150/disk_140/sbprolog/sbprolog.doc

Text File | 1992-05-06 | 158KB | 6,997 lines

                   The SB-Prolog System, Version 2.2

                             A User Manual

                               edited by
                            Saumya K. Debray

                            from material by

                           David Scott Warren
                            Suzanne Dietrich
                          SUNY at Stony Brook

                            Fernando Pereira
                           SRI International



                               March 1987


                     Department of Computer Science
                         University of Arizona
                            Tucson, AZ 85721











































                   The SB-Prolog System, Version 2.2

                             A User Manual









      Abstract: SB-Prolog is a  public-domain  Prolog  system  for

      Unix-  based  systems  originally  developed  at SUNY, Stony

      Brook.  The core of the system is an emulator, written in  C

      for  portability,  of  a  Prolog  virtual machine that is an

      extension of the Warren Abstract Machine.  The remainder  of

      the system, including the translator from Prolog to the vir-

      tual machine instructions, is written in Prolog.   Parts  of

      this  manual, specifically the sections on Prolog syntax and

      descriptions of some of the builtins, are based  on  the  C-

      Prolog User Manual by Fernando Pereira.









      ____________________
         - Unix is a trademark of AT&T.


















1.  Introduction




     SB-Prolog is a public domain Prolog system based on  an  extension  of

the Warren Abstract Machine[1].  The WAM  simulator  is  written  in  C  to

enhance portability.  Prolog source programs can be compiled into byte code

files, which contain encodings of WAM instructions and are  interpreted  by

the simulator.  Programs can also be interpreted via consult.


     SB-Prolog offers several features that are not found  on  most  Prolog

systems  currently  available.  These include: compilation to object files;

dynamic loading of predicates; provision for generating executable code  on

the  global  stack,  which  can  be  later be reclaimed; an extension table

facility that permits memoization of  relations.   Other  features  include

full  integration between compiled and interpreted code, and a facility for

the definition and expansion of macros that is fully  compatible  with  the

runtime system.


     The following features are absent: we expect to  incorporate  them  in

future versions.


     A ``listing'' feature, which produces a listing of clauses in the sys-

     tem database.


     A garbage collector for the global stack.

____________________
   [1] D. H. D. Warren, ``An Abstract Prolog Instruction Set'', Tech.  Note
309, SRI International, 1983.





                                     1












     The            record/recorded/erase,            clause            and

     current_atom/current_functor/current_predicate facilities of C-Prolog.


     In addition, it should be mentioned that while  interpreted  and  com-

piled code behave similarly in almost all cases, there are a few cases that

we are aware of where they behave differently:


(1)  In cuts buried within if-then-elses (->): such  cuts  are  treated  as

     ``hard''  cuts in interpreted code (i.e. cuts away alternative clauses

     as well), but as ``soft'' cuts in compiled code (i.e. cuts as far back

     as the head of the clause, but does not cut away alternative clauses).


(2)  In the evaluation of arithmetic expressions involving compound  subex-

     pressions  created  dynamically: in compiled code, this cannot be han-

     dled using is/2, and must be handled using eval/2 (see the section  on

     Arithmetic  predicates),  while  in  interpreted  code  either is/2 or

     eval/2 is acceptable.























                                     2












2.  Getting Started




     This section is intended to give a broad  overview  of  the  SB-Prolog

system,  so  as  to  enable  the  new user to begin using the system with a

minimum of delay.  Many of the  topics  touched  on  here  are  covered  in

greater depth in later sections.


2.1.  The Dynamic Loader Search Path




     In SB-Prolog, it is not necessary for the user to load all the  predi-

cates  necessary  to execute a program.  Instead, if an undefined predicate

foo is encountered during execution, the system searches the user's  direc-

tories  in the order specified by the environment variable SIMPATH until it

finds a directory containing a file foo whose name is that of the undefined

predicate.   It  then  dynamically  loads  and links the file foo (which is

expected to be a byte code file defining the predicate foo), and  continues

with execution; if no such file can be found, an error message is given and

execution fails.  This feature makes it unnecessary for the user to have to

explicitly link in all the predicates that might be necessary in a program:

instead, only those files are loaded which are necessary to have  the  pro-

gram  execute.   This  can  significantly reduce the memory requirements of

programs.


     The key to this  dynamic  search-and-load  behaviour  is  the  SIMPATH

environment variable, which specifies the order in which directories are to

be searched.  It may be set by adding the  following  line  to  the  user's


                                     3












.cshrc file:



            setenv SIMPATH path




where path is a sequence of directory names separated by colons:



            dir<1>:dir<2>: ... :dir<n>




and dir<i> are full path names to the respective directories.  For example,

executing the command

            setenv SIMPATH .:$HOME/prolog/modlib:$HOME/prolog/lib




sets the search order for undefined predicates to the following: first, the

directory in which the program is executing is searched; if the appropriate

file is not found in this  directory,  the  directories  searched  are,  in

order,  ~/prolog/modlib  and  ~/prolog/lib.  If the appropriate file is not

found in any of these directories, the system gives an  error  message  and

execution fails.


     The beginning user  is  advised  to  include  the  system  directories

(listed  in the next section) in his SIMPATH, in order to be able to access

the system libraries (see below).








                                     4












2.2.  System Directories




     There are four basic system directories: cmplib, lib, modlib and  sim.

cmplib  contains the Prolog to byte code translator; lib and modlib contain

library routines.  The src subdirectory  in  each  of  these  contains  the

corresponding Prolog source programs.  The directory sim contains the simu-

lator, the subdirectory builtin contains code for the builtin predicates of

the system.


     It is recommended that the beginning user include  the  system  direc-

tories in his SIMPATH, by setting SIMPATH to

                      .:SBP/modlib:SBP/lib:SBP/cmplib


where SBP denotes the path to the root of the SB-Prolog system directories.


2.3.  Invoking the Simulator




     The simulator is invoked by the command

            sbprolog bc_file


where bc_file is a byte code file resulting from the compilation of a  Pro-

log  program.  In almost all cases, the user will wish to interact with the

SB-Prolog query evaluator, in which case bc_file will be $readloop, and the

command will be

    sbprolog PATH/\$readloop


where PATH is the path to the directory containing the command  interpreter



                                     5












$readloop.  This directory, typically, is modlib (see Section 2.2 above).


     The command interpreter reads in a query typed in by the user,  evalu-

ates  it  and  prints  the answer(s), repeating this until it encounters an

end-of-file (the standard end-of-file character on the system,  e.g.  ctrl-

D), or the user types in end_of_file or halt.


     The user should ensure that the the directory containing  the  execut-

able  file sim (typically, the system directory sim: see Section 2.2 above)

is included in the shell variable path; if not, the full path to the  simu-

lator will have to be specified.


     In general, the simulator may be invoked with a variety of options, as

follows:

             sbprolog -options bc_file
    or
             sbprolog -option<1> -option<2> ... -option<n> bc_file


The options recognized by the simulator are described in Section 4.2.


     When called with a byte code file bc_file, the simulator begins execu-

tion  with the first clause in that file.  The first clause in such a file,

therefore, should be a clause without any arguments in the head (otherwise,

the  simulator  will  attempt  to dereference argument pointers in the head

that are really pointing into deep space, and usually come to a  sad  end).

If  the  user is executing a file in this manner rather than using the com-

mand interpreter, he should also be careful to include the undefined predi-

cate  handler  `_$undefined_pred'/1,  which is normally defined in the file

modlib/$init_sys.P.



                                     6












2.4.  Executing Programs




     There are two ways of executing a program: a source file may  be  com-

piled into a byte-code file, which can then be loaded and executed; or, the

source file may be interpreted  via  consult.   The  system  supports  full

integration  of compiled and interpreted code, so that some predicates of a

program may be compiled, while others may  be  interpreted.   However,  the

unit  of compilation or consulting remains the file.  The remainder of this

section describes each of these procedures in more detail.


2.4.1.  Compiling Programs




     The compiler is invoked through  the  Prolog  predicate  compile.   It

translates  Prolog source programs into byte code that can then be executed

on the simulator.  The compiler may be invoked as follows:



            | ?- compile(InFile [, OutFile ] [, OptionsList ]).
    or
            | ?- compile(InFile, OutFile, OptionsList, PredList).




where optional parameters are enclosed in brackets.  InFile is the name  of

the  input (i.e. source) file; OutFile is the name of the output file (i.e.

byte code) file; OptionsList is a list of compiler options, and PredList is

a list of terms P/N denoting the predicates defined in InFile, where P is a

predicate name and N its arity.




                                     7












     The input and output file names must  be  Prolog  atoms,  i.e.  either

begin  with a lower case letter and consist only of letters, digits, dollar

signs and underscores; or, be enclosed within single quotes.  If the output

file  name  is  not  specified,  it  defaults  to  InFile.out.  The list of

options, if specified, is a Prolog list, i.e. a term of the form



            [ option<1>, option<2>, ..., option<n> ].




If left unspecified, it defaults to the empty list [].  PredList, if speci-

fied,  is usually given as an uninstantiated variable; its principal use is

for setting trace points on the predicates in the file (see Sections 6  and

8).  Notice that PredList can only appear in compile/4.


     A list of compiler options appears in Section 8.3.


2.4.2.  Loading Byte Code Files




Byte code files may be loaded into the simulator using the predicate load:



            | ?- load(ByteCode_File).




where ByteCode_File is a Prolog atom (see Section 3.1) that is the name  of

a byte code file.


     The load predicate invokes the dynamic loader,  which  carries  out  a

search  according  to  the  sequence  specified by the environment variable


                                     8












SIMPATH (see Section 2.1).  It is therefore not necessary to always specify

the full path name to the file to be loaded.


     Byte code files may be concatenated together  to  produce  other  byte

code  files.   Thus,  for  example,  if  foo1  and foo2 are byte code files

resulting from the compilation of two Prolog source programs, then the file

foo, obtained by executing the shell command

             cat foo1 foo2 > foo


is a byte code file as well, and may be loaded and executed.  In this case,

loading  and  executing  the file foo would give the same result as loading

foo1 and foo2 separately, which in turn would be the same as  concatenating

the  original  source  files and compiling this larger file.  This makes it

easier to compile large programs: one need only  break  them  into  smaller

pieces,  compile  the individual pieces, and concatenate the resulting byte

code files together.


2.4.3.  Consulting Programs




     Instead of compiling a file to generate a byte code  file  which  then

has  to  be  loaded, a program may be executed interpretively by ``consult-

ing'' the corresponding source file:

            | ?- consult(SourceFile [, OptionList ] ).
    or
            | ?- consult(SourceFile, OptionList, PredList).


where SourceFile is a Prolog atom which is the name of a file containing  a

Prolog  source  program;  OptionList  is  a list of options to consult; and



                                     9












PredList is a list of terms P/N, where P is a  predicate  name  and  N  its

arity, specifying which predicates have been consulted from SourceFile; its

principal use is for setting trace points on the  predicates  in  the  file

(see Section 6).  Notice that PredList can only appear in consult/3.


     At this point, the options recognized for consult are the following:


first


     If on, causes each clause read in to be added as the first  clause  of

     the  database  (so that effectively, the clauses appear in the reverse

     order as in the source file).  Default: off.


index


     If on, causes an index to be generated on the first argument  of  each

     predicate.  Default: off.


index(N)

     If on, causes an index to be generated on the N[th] argument  of  each

     predicate.  Default: off.


q    ``quick''.  If on, invokes a consultation algorithm  that  is  simpler

     and  more efficient than the general one.  However, the code generated

     with the simpler algorithm may not be correct if  there  are  repeated

     variables within compound terms in the body of the clause, e.g. in

                 p(X) :- q([X, X]).


     Default: off.




                                    10












t    ``trace''.  Causes a trace point to be set on  any  predicate  in  the

     current file that does not already have a trace point set.


v    ``verbose''.  Causes information regarding which predicates have  been

     consulted to be printed out. Default: off.


In addition to the above, the options specified for the macro expander  are

also recognized (see Section 10)).


     It is important to note that SB-Prolog's consult predicate is  similar

to  that  of  Quintus  Prolog, and behaves like C-Prolog's reconsult.  This

means that if a predicate is defined across two or more  files,  consulting

them will result in only the clauses in the file consulted last being used.


2.5.  Execution Directives




     Execution directives may be specified to compile and  consult  through

:-/1.   If,  in the read phase of compile or consult, a term with principal

functor :-/1 is read in, this term is executed directly via  call/1.   This

enables  the  user  to  dynamically  modify  the  environment,  e.g. via op

declarations (see Section 3.2), asserts etc.


     A point to note is that if the environment is modified as a result  of

an execution directive, the modifications are visible only in that environ-

ment.  This means that consulted code, which runs  in  the  environment  in

which  the  source program is read in (and which is modified by such execu-

tion directives) feel the effects of such execution  directives.   However,

byte  code  resulting  from  compilation, which, in general, executes in an


                                    11












environment different from that in which the source was compiled, does  not

inherit  the  effects  of  such directives.  Thus, an op declaration can be

used in a source file to change the syntax and allow the remainder  of  the

program  to  be  parsed  according  to  the modified syntax; however, these

modifications will not, in general, manifest themselves if the byte code is

executed  in  another  environment.   Of course, if the byte code is loaded

into the same environment as that in which the source program was compiled,

e.g. through

            | ?- compile(foo, bar), load(bar).


the effects of execution directives will continue to be felt.


3.  Syntax




3.1.  Terms




     The syntax of SB-Prolog is by and large compatible  with  that  of  C-

Prolog.   The  data objects of the language are called  terms.  A  term  is

either a constant, a  variable  or  a  compound  term.   Constants  can  be

integers  or  atoms.   The  symbol for an atom must begin with a lower case

letter or the dollar sign $, and consist of any number of letters,  digits,

underscores  and  dollar  signs;  if  it  contains any character other than

these,  it  must  be  enclosed  within  single  quotes.[2]  As   in   other
____________________
   [2] Users are advised against using symbols beginning with `$' or  `_$',
however,  in  order  to  minimize the possibility of conflicts with symbols
internal to the system.




                                    12












programming languages,  constants  are definite elementary objects.


     Variables are distinguished by an initial capital  letter  or  by  the

initial character "_", for example

    X   Value   A   A1   _3   _RESULT   _result


If a variable is only referred to once, it does not need to  be  named  and

may  be  written as an anonymous variable, indicated by the underline char-

acter "_".


     A variable should be thought of as  standing  for  some  definite  but

unidentified   object.   A  variable  is  not  simply  a  writeable storage

location  as  in  most programming languages;  rather it is  a  local  name

for  some  data  object,  cf.   the  variable  of  pure  LISP  and constant

declarations in Pascal.


     The structured data objects of the language are the compound terms.  A

compound  term  comprises  a  functor  (called the principal functor of the

term) and a sequence of one or more terms called arguments.  A  functor  is

characterised  by  its  name,  which is an atom, and its arity or number of

arguments.  For example the compound term whose functor is named `point' of

arity 3, with arguments X, Y and Z, is written

    point(X,Y,Z)


An atom is considered to be a functor of arity 0.


     A functor or predicate symbol is uniquely identified by its  name  and

arity  (in  other  words,  it is possible for different symbols having dif-

ferent arities to share the same name).  A functor or  predicate  symbol  p


                                    13












with arity n is usually written p/n.


     One  may  think  of  a  functor  as  a record type and  the  arguments

of a compound term as the  fields  of  a  record.   Compound terms are use-

fully pictured as trees.  For example, the term

    s(np(john),vp(v(likes),np(mary)))


would be pictured as the structure

                                     s
                                   /  \
                                np      vp
                                |      /  \
                              john    v    np
                                      |    |
                                   likes  mary



     Sometimes it is convenient to write certain functors as  operators  --

2-ary  functors  may  be  declared as infix operators and 1-ary functors as

prefix or postfix operators.  Thus it is possible to write

    X+Y     (P;Q)     X<Y      +X     P;


as optional alternatives to

    +(X,Y)   ;(P,Q)   <(X,Y)   +(X)   ;(P)


Operators are described fully in the next section.


     Lists form an important class of data structures in Prolog.  They  are

essentially   the  same  as  the  lists  of LISP: a list either is the atom

[], representing the empty list, or  is  a  compound  term   with   functor

`.'/2  and   two   arguments  which  are  respectively the head and tail of

the list.  Thus  a  list  of  the  first  three  natural  numbers  is   the



                                    14












structure

                                      .
                                    / \
                                  1    .
                                      / \
                                    2    .
                                       / \
                                     3   []


which could be written, using the standard syntax, as

    .(1,.(2,.(3,[])))


but which is normally written, in a special list notation, as [1,2,3].  The

special list notation in the case when the tail of  a  list  is  a variable

is exemplified by

    [X|L]     [a,b|L]


representing

                             .               .
                            / \             / \
                           X   L           a   .
                                              / \
                                             b   L


respectively.


     Note that this list syntax is only syntactic sugar for  terms  of  the

form  `.'(_,_) and does not provide any new facilities that were not avail-

able otherwise.


     For convenience, a further   notational   variant   is   allowed   for

lists   of   integers   which  correspond  to ASCII character codes.  Lists

written in this notation are called strings.  For example,




                                    15











    "Prolog"


represents exactly the same list as

    [80,114,111,108,111,103]



3.2.  Operators




     Operators in Prolog are simply a notational convenience.  For example,

the expression

    2 + 1


could also be written +(2,1).  It should be noticed  that  this  expression

represents the structure

                                     +
                                   /   \
                                  2     1


and not the number 3.  The addition would only be performed if  the  struc-

ture  was passed as an argument to an appropriate procedure (such as eval/2

- see Section 5.2).


     The Prolog syntax caters for operators   of   three   main   kinds   -

infix, prefix and postfix.  An infix operator appears between its two argu-

ments, while a prefix operator precedes its single argument and  a  postfix

operator is written after its single argument.


     Each operator has a precedence, which is a number from  1   to   1200.

The  precedence  is  used  to  disambiguate expressions  where  the  struc-

ture  of  the  term  denoted is not made explicit through parenthesization.



                                    16












The   general  rule is that the operator with the highest precedence is the

principal functor.  Thus if `+'  has  a higher precedence  than  `/',  then

``a+b/c'' and ``a+(b/c)'' are equivalent and denote the term "+(a,/(b,c))".

Note that the  infix form of the term "/(+(a,b),c)" must  be  written  with

explicit parentheses, ``(a+b)/c''.


     If there are two operators in  the  subexpression  having   the   same

highest   precedence,  the ambiguity must be resolved from the types of the

operators.  The possible types for an infix operator are

    xfx     xfy     yfx


With an operator of type `xfx', it is a requirement that both  of  the  two

subexpressions  which  are  the  arguments of the operator must be of lower

precedence  than  the  operator  itself,  i.e.   their  principal  functors

must   be   of   lower   precedence, unless the subexpression is explicitly

bracketed  (which  gives  it  zero  precedence).  With  an operator of type

`xfy',  only  the  first  or  left-hand subexpression must be of lower pre-

cedence;  the second can be of the same  precedence  as the main  operator;

and vice versa for an operator of type `yfx'.


     For example, if the operators `+' and `-' both  have  type  `yfx'  and

are  of  the  same  precedence, then the expression ``a-b+c'' is valid, and

means ``(a-b)+c'', i.e. ``+(-(a,b),c)''.  Note that the expression would be

invalid  if  the   operators   had  type `xfx', and would mean ``a-(b+c)'',

i.e. ``-(a,+(b,c))'', if the types were both `xfy'.


     The possible types for a prefix operator are




                                    17











    fx        fy


and for a postfix operator they are

    xf        yf


The meaning of the types should be clear  by   analogy   with   those   for

infix   operators.    As   an  example,  if `not' were declared as a prefix

operator of type `fy', then

    not not P


would be a permissible way to write  "not(not(P))".  If   the   type   were

`fx', the preceding expression would not be legal, although

    not P


would still be a permissible form for "not(P)".


     In SB-Prolog, a functor named name is  declared  as   an  operator  of

type type and precedence precedence by calling the evaluable predicate op:

            | ?- op(precedence,type,name).


The argument name can also be a list of names of operators of the same type

and precedence.


     It is possible to have more than one operator of the  same   name,  so

long  as  they  are of different kinds, i.e.  infix, prefix or postfix.  An

operator of any kind may be redefined by a new declaration   of   the  same

kind.    This   applies equally to operators which are provided as standard

in SB-Prolog, namely:

    :- op(   1200,   xfx,   [ :-, --> ]).
    :- op(   1200,    fx,   [ :-, ?- ]).
    :- op(   1198,   xfx,   [ ::- ]).


                                    18





    :- op(   1100,   xfy,   [ ; ]).
    :- op(   1050,   xfy,   [ -> ]).
    :- op(   1000,   xfy,   [ ',' ]).   /* See note below */
    :- op(    900,    fy,   [ not, \+, spy, nospy ]).
    :- op(    700,   xfx,   [ =, is, =.., ==, \==, @<, @>, @=<, @>=,
                              =:=, =\=, <, >, =<, >= ]).
    :- op(    661,   xfy,   [ `.' ]).
    :- op(    500,   yfx,   [ +, -, /\, \/ ]).
    :- op(    500,    fx,   [ +, - ]).
    :- op(    400,   yfx,   [ *, /, //, <<, >> ]).
    :- op(    300,   xfx,   [ mod ]).
    :- op(    200,   xfy,   [ ^ ]).




     Operator declarations are most usefully placed in  directives  at  the

top  of  your program files. In this case the directive should be a command

as shown above. Another common method of organisation is to have  one  file

just  containing commands to declare all the necessary operators. This file

is then always consulted first.


     Note that a comma written literally as  a  punctuation  character  can

be  used  as  though  it were an infix operator of precedence 1000 and type

`xfy':

    X,Y    ','(X,Y)


represent the same compound term.  But note that  a  comma  written  as   a

quoted atom is not a standard operator.


     Note also that the  arguments  of   a   compound   term   written   in

standard   syntax  must be expressions of precedence below 1000. Thus it is

necessary to parenthesize the expression "P :- Q" in

    assert((P :- Q))


The following syntax restrictions  serve   to  remove  potential  ambiguity

associated with prefix operators.


-    In a term written in standard syntax, the  principal  functor  and its

     following  "("  must  not be separated by any whitespace.  Thus


                                    19











         point (X,Y,Z)


     is invalid syntax (unless point were declared as a prefix operator).


-    If the argument of a prefix operator starts with  a  "(",   this   "("

     must  be  separated  from  the operator by at least one space or other

     non-printable character.  Thus

         :-(p;q),r.


     (where `:-' is the prefix operator) is invalid  syntax,  and  must  be

     written as

         :- (p;q),r.



-    If a prefix  operator  is  written  without   an   argument,   as   an

     ordinary  atom,  the  atom  is  treated  as  an expression of the same

     precedence as the prefix operator, and  must  therefore  be  bracketed

     where necessary.  Thus the brackets are necessary in

         X = (?-)



4.  SB-Prolog: Operational Semantics




4.1.  Standard Execution Behaviour




     The normal execution behaviour of SB-Prolog follows the usual left  to

right  order  of  literals  within  a clause, and the textual top to bottom

order of clauses for a predicate.  This corresponds to a depth first search

of  the leftmost SLD-tree for the program and the given query.  Unification


                                    20












without occurs check is used, and execution backtracks to the  most  recent

choice point when unification fails.


4.2.  Cuts and If-Then-Else




     This standard execution behaviour of SB-Prolog can  be  changed  using

constructs  like cut (`!') and if-then-else (`->').  In SB-Prolog, cuts are

usually treated as hard, i.e. discard choice points of all the literals  to

the  left  of  the cut in the clause containing the cut being executed, and

also the choice point for the parent predicate, i.e.  any remaining clauses

for the predicate containing the cut being executed.  There are some situa-

tions, however, where the scope of a cut is restricted to be  smaller  than

this.  Restrictions apply under the following conditions:


(1)  The cut occurs in a term which has been  constructed  at  runtime  and

     called through call/1, e.g. in

                   ..., X = (p(Y), !, q(Y)), ..., call(X), ...


     In this case, the scope of the cut is  restricted  to  be  within  the

     call,  unless  one of the following cases also apply and serve to res-

     trict its scope further.


(2)  The cut occurs in a negated goal, or within the scope of  an  if-then-

     else.  In these cases, the scope of the cut is restricted to be within

     the negation or the if-then-else.


In cases involving nested occurrences of these situations, the scope of the

cut  is restricted to that for the deepest such nested construct, i.e. most


                                    21












restricted.  For example, in the construct

 ..., not( (p(X) -> not( (q(X), (r(X) -> s(X) ; (t(X), !, u(X)))) )) ), ...


the scope of the cut is restricted to the inner if-then-else, and does  not

affect any choice point that may have been set up for q(X).


     The behaviour of the if-then-else operator `->' is  as  follows:  when

executing the goal

                                P -> Q ; R


if P succeeds, then any alternatives for P are discarded and  Q  is  tried,

while if P fails then R is tried.  Thus, -> may be thought of as



            P -> Q ; R :- P, !, Q.
            P -> Q ; R :- R.




The scoping of cuts within if-then-elses is consistent with this  conceptu-

alization.


4.3.  Unification of Floating Point Numbers




     As far as unification  is  concerned,  no  type  distinction  is  made

between  integers  and floating point numbers, and no explicit type conver-

sion is necessary when unifying an integer with a float.  However,  due  to

the  finite  precision representation of floating point numbers and cumula-

tive round-off errors in floating point arithmetic,  comparisons  involving

floating point numbers may not always give the expected results.  An effort



                                    22












is made to minimize surprises by considering two numbers x and y (at  least

one of which is a float) to be unifiable if ||x| - |y||/min(|x|, |y|) to be

less than 10[-5].   However,  this  does  not  guarantee  immunity  against

round-off  errors.   For the same reason, users are warned that indexing on

predicate arguments (see Section 13) may not give the expected  results  if

floating point numbers are involved.










































                                    23












5.  Evaluable Predicates




     This section describes (most of) the evaluable predicates provided  by

SB-Prolog.   These  can  be  divided into three classes: inline predicates,

builtin predicates and library predicates.


     Inline predicates  represent  ``primitive''  operations  in  the  WAM.

Calls to inline predicates are compiled into a sequence of WAM instructions

in-line, i.e. without actually making a call to the predicate.   Thus,  for

example, relational predicates (>/2, >=/2, etc.) compile to, essentially, a

subtraction and a conditional branch.  Inline predicates  cannot  be  rede-

fined by the user.  Table 1 lists the SB-Prolog inline predicates.


     Unlike inline predicates, builtin  predicates  are  implemented  by  C

functions  in the simulator, and accessed via the inline predicate `_$buil-

tin'/1.  Thus, if a builtin predicate foo/3 was defined as  builtin  number

38, there would be a definition in the system of the form





=/2                 </2                  =</2                 >=/2
>/2                 /\/2                 `\/'/2               <</2
>>/2                =:=/2                =\=/2                is/2
/1                  `_$savecp'/1         `_$cutto'/1          `_$builtin'/1
`_$call'/1          nonvar/1             var/1                fail/0
halt/0              true/0


                  Table 1: Inline Predicates of SB-Prolog







                                    24











            foo(X,Y,Z) :- '_$builtin'(38).





     In effect, a builtin is simply a segment of code in a large case (i.e.

switch)  statement.   Each  builtin is identified internally by an integer,

referred to as its ``builtin number'', associated with it.  The code for  a

builtin  with builtin number k corresponds to the k[th.] case in the switch

statement.  SB-Prolog limits the total number of builtins to 256.


     Builtins, unlike inline predicates,  can be  redefined  by  the  user.

For example, the predicate foo/3 above can be redefined simply by compiling

the new definition into a directory such that during dynamic  loading,  the

new definition would be encountered first and loaded.


     A list of the builtins currently provided is  listed  in  Appendix  1.

Section  7.4  describes the procedure to be followed in order to define new

builtin predicates.


     Like builtin predicates, library predicates may also be  redefined  by

the  user.  The essential difference between builtin and library predicates

is that whereas the former are coded into the simulator in  C,  the  latter

are written in Prolog.


5.1.  Input and Output




     Input and output are done with respect to the current input and output

streams.  These can be set, reset or checked using the file handling predi-

cates described below.  The default input and output streams are denoted by


                                    25












user, and refer to the user's terminal.


5.1.1.  File Handling




see(F)

     F becomes the current input stream.  F must be instantiated to an atom

     at the time of the call.


seeing(F)

     F is unified with the name of the current input file.


seen Closes the current input stream.


tell(F)

     F becomes the current output stream.  F must  be  instantiated  to  an

     atom at the time of the call.


telling(F)

     F is unified with the name of the current output file.


told


     Closes the current output stream.


$exists(F)

     Succeeds if file F exists.









                                    26












5.1.2.  Term I/O




read(X)

     The next term, delimited by a full stop (i.e.  a "."  followed   by  a

     carriage-return  or   a   space),   is   read   from the current input

     stream and unified with X. The syntax of the term  must  accord   with

     current  operator  declarations.   If a call read(X) causes the end of

     the current input stream to be reached, X is unified  with  the   atom

     `end_of_file'.   Further  calls  to read for the same stream will then

     cause an error failure.


write(X)

     The term X is written to the  current  output  stream   according   to

     operator declarations in force.


display(X)

     The term X is displayed on the terminal in standard parenthesised pre-

     fix notation.


writeq(Term)

     Similar to write(Term), but the names of atoms and functors are quoted

     where necessary to make the result acceptable as input to read.


print(Term)

     Prints out the term Term onto the user's terminal.


writename(Term)

     If Term is an uninstantiated variable, its name,  which  looks  a  lot


                                    27












     like  an  address  in memory, is written out; otherwise, the principal

     functor of Term is written out.


writeqname(Term)

     As for writename, but the names are quoted where necessary.


print_al(N, A)


     Prints A (which must be an atom or a number) left-aligned in  a  field

     of  width  N,  with  blanks padded to the right.  If A's print name is

     longer than the field width N, then A is printed  but  with  no  right

     padding.


print_ar(N, A)


     Prints A (which must be an atom or a number) right-aligned in a  field

     of  width  N,  with  blanks  padded to the left.  If A's print name is

     longer than the field width N, then A is printed but with no left pad-

     ding.


5.1.3.  Character I/O




nl   A new line is started on the current output stream.


get0(N)

     N is the ASCII code of the next  character  from  the  current   input

     stream.  If  the current input stream reaches its end of file, a -1 is

     returned (however, unlike in C-Prolog, the input stream is not  closed

     on encountering end-of-file).


                                    28












get(N)

     N is the ASCII code of the  next  non-blank  printable  character from

     the  current input stream. It has the same behaviour as get0 on end of

     file.


put(N)

     ASCII character code N is output to the current output stream.  N must

     be an integer.


tab(N)

     N spaces are output to the  current  output  stream.   N  must  be  an

     integer.


5.2.  Arithmetic




     Arithmetic is performed by   evaluable  predicates   which   take   as

arguments    arithmetic  expressions   and  evaluate  them.  An  arithmetic

expression is a term  built  from  evaluable functors, numbers   and  vari-

ables.   At   the   time   of  evaluation,  each  variable in an arithmetic

expression must be bound to a number or  to   an   arithmetic   expression.

Each evaluable functor stands for an arithmetic  operation.


     The evaluable  functors  are  as  follows,   where   X   and   Y   are

arithmetic expressions.


X + Y

     addition.




                                    29












X - Y

     subtraction.


X * Y

     multiplication.


X / Y

     division.[3]  Amounts  to  integer  division  if  both  X  and  Y  are

     integers.


X mod Y

     X (integer) modulo Y.


-X   unary minus.


X /\ Y

     integer bitwise conjunction.


X \/ Y

     integer bitwise disjunction.


X << Y

     integer bitwise left shift of X by Y places.


X >> Y

     integer bitwise right shift of X by Y places.


____________________
   [3] The ``integer division'' operator `//' of C-Prolog is not supported;
it can be faked using floor/2 if necessary.





                                    30












\X   integer bitwise negation.


     As far as unification  is  concerned,  no  type  distinction  is  made

between  integers  and floating point numbers, and no explicit type conver-

sion is necessary when unifying an integer with a float.  However,  due  to

the  finite  precision representation of floating point numbers and cumula-

tive round-off errors in floating point arithmetic,  comparisons  involving

floating point numbers may not always give the expected results.  An effort

is made to minimize surprises by considering two numbers x and y (at  least

one  of  which  is  a float) to be unifiable if |x - y|/min(|x|, |y|) to be

less than 10[-5].  The user  should  note,  however,  that  this  does  not

guarantee immunity against round-off errors.


     The arithmetic evaluable predicates are as  follows,  where  X  and  Y

stand  for  arithmetic  expressions,  and  Z for some term.  Note that this

means that is only evaluates one of its arguments as an arithmetic  expres-

sion  (the  right-hand  side  one),  whereas  all the comparison predicates

evaluate both their arguments.


Z is X


     Arithmetic expression X is evaluated and the result, is  unified  with

     Z.  Fails  if X is not an arithmetic expression.  One point to note is

     that in compiled code, the current implementation of is/2 cannot  han-

     dle compound expressions created dynamically: these have to be handled

     using eval/2.  Thus, for example, the goals

                    ..., X = Y + Z, Y = 3, Z = 2, W is X, ...




                                    31












     would fail, whereas

                  ..., X = Y + Z, Y = 3, Z = 2, eval(X,W), ...


     could succeed.


eval(E, X)

     Evaluates the arithmetic expression E and unifies the result with  the

     term  X.   Fails  if E is not an arithmetic expression.  The principal

     difference between eval/2 and is/2 is that in compiled code, is/2 can-

     not  handle arithmetic expressions that are compound terms constructed

     at runtime, but eval/2 can.  On the other hand, is/2 is more efficient

     for  the  evaluation  of static arithmetic expressions (i.  e. expres-

     sions that do not have compound subterms created at runtime).  Another

     difference  is  that while is/2 is an inline predicate, eval/2 is not;

     thus, is/2 cannot be redefined by the user, but eval/2 can.


X =:= Y


     The values of X and Y are equal.  If either X or  Y  involve  compound

     subexpressions  that  are  created  at  runtime,  they should first be

     evaluated using eval/2.


X =\= Y


     The values of X and Y are not equal.  If either X or  Y  involve  com-

     pound subexpressions that are created at runtime, they should first be

     evaluated using eval/2.






                                    32












X < Y


     The value of X is less than the value of Y.  If either X or Y  involve

     compound subexpressions that are created at runtime, they should first

     be evaluated using eval/2.


X > Y


     The value of X is greater than the value of  Y.   If  either  X  or  Y

     involve  compound  subexpressions  that  are  created at runtime, they

     should first be evaluated using eval/2.


X =< Y


     The value of X is less than or equal to the value of Y.  If  either  X

     or Y involve compound subexpressions that are created at runtime, they

     should first be evaluated using eval/2.


X >= Y


     The value of X is greater than or equal to the value of Y.  If  either

     X  or  Y  involve compound subexpressions that are created at runtime,

     they should first be evaluated using eval/2.


floor(X, Y)


     If X is a floating point number in the call and Y is free, then  Y  is

     instantiated  to  the  largest  integer  whose  absolute  value is not

     greater than the absolute value of X; if X is  uninstantiated  in  the

     call and Y is an integer, then X is instantiated to the smallest float



                                    33












     not less than Y.


floatc(F, M, E)


     If F is a number while M and E are uninstantiated in the call, then  M

     is  instantiated  to a float m (of magnitude less than 1), and E to an

     integer n, such that

                                 F = m * 2[n].


     If F is uninstantiated in the call  while  M  is  a  float  and  E  an

     integer, then F becomes instantiated to M * 2[E].


exp(X, Y)


     If X is instantiated to a number and Y is uninstantiated in the  call,

     then  Y  is instantiated to e[X] (where e = 2.71828...); if X is unin-

     stantiated in the call while Y is instantiated to a  positive  number,

     then X is instantiated to log<e>(Y).


square(X, Y)


     If X is instantiated to a number while  Y  is  uninstantiated  in  the

     call,  then  Y becomes instantiated to X[2]; if X is uninstantiated in

     the call while Y is instantiated to a positive number, then X  becomes

     instantiated to the positive square root of Y (if Y is negative in the

     call, X becomes instantiated to 0.0).


sin(X, Y)






                                    34












     If X is instantiated to a number (representing an  angle  in  radians)

     and  Y  is  uninstantiated in the call, then Y becomes instantiated to

     sin(X) (the user should check the magnitude of X to make sure that the

     result is meaningful).  If Y is instantiated to a number between -~~/2

     and ~~/2 and X is uninstantiated in the call, then X  becomes  instan-

     tiated to sin[-1](Y).


5.3.  Convenience




P , Q

     P and then Q.


P ; Q

     P or Q.


     Always  succeeds.


X = Y

     Defined as if by the clause " Z=Z ", i.e. X and Y are unified.


5.4.  Extra Control




!    Cut (discard) all choice points made since  the  parent  goal  started

     execution.   (The  scope  of cut in different contexts is discussed in

     Section 4.2).


not P

     If the goal P has a solution,  fail,   otherwise   succeed.    It   is


                                    35












     defined as if by

         not(P) :- P, !, fail.
         not(_).



P -> Q ; R

     Analogous to "if P then Q else R" i.e.  defined as if by

         P -> Q ; R :- P, !, Q.
         P -> Q ; R :- R.



P -> Q

     When occurring other  than  as  one  of  the  alternatives  of  a dis-

     junction, is equivalent to

         P -> Q ; fail.



repeat

     Generates an  infinite  sequence  of  backtracking  choices.    It  is

     defined by the clauses:

         repeat.
         repeat :- repeat.



fail Always fails.


5.5.  Meta-Logical




var(X)

     Tests whether X is currently instantiated to a variable.





                                    36












nonvar(X)

     Tests whether X is currently instantiated to a non-variable term.


atom(X)

     Checks that X is  currently  instantiated  to   an   atom   (i.e.    a

     non-variable term of arity 0, other than a number).


integer(X)

     Checks that X is currently instantiated to an integer.


real(X)


     Checks that X is currently instantiated to a floating point number..


number(X)

     Checks that X is currently instantiated to a number, i.e. that  it  is

     either an integer or a real.


atomic(X)

     Checks that X is currently instantiated to an atom or number.


structure(X)


     Checks that X is currently instantiated to a compound term, i.e. to  a

     nonvariable term that is not atomic.


functor(T,F,N)

     The principal functor of term T has name F and arity N,  where   F  is

     either   an   atom  or, provided N is 0, a number. Initially, either T

     must  be  instantiated  to  a  non-variable,  or  F  and  N   must  be



                                    37












     instantiated    to,    respectively,   either   an   atom  and  a non-

     negative integer or an integer and 0.  If  these  conditions  are  not

     satisfied,  an  error  message  is given.  In the case where T is ini-

     tially instantiated to a variable, the result  of  the   call   is  to

     instantiate   T  to the most general term having the principal functor

     indicated.


arg(I,T,X)

     Initially, I must be instantiated to a positive integer and  T   to  a

     compound   term.   The  result  of the call is to unify X with the Ith

     argument of term  T.  (The  arguments  are  numbered from  1 upwards.)

     If  the initial conditions are not satisfied or I is out of range, the

     call merely fails.


X =.. Y

     Y is a list whose head is the  atom  corresponding  to  the  principal

     functor   of  X and whose tail is the argument list of that functor in

     X. E.g.

         product(0,N,N-1) =.. [product,0,N,N-1]

         N-1 =.. [-,N,1]

         product =.. [product]


     If X is instantiated to a variable, then Y must be instantiated either

     to a list of determinate length whose head is an atom, or to a list of

     length 1 whose head is a number.


name(X,L)

     If X is an atom or a number then L is a list of the ASCII codes of the


                                    38












     characters comprising the name of X. E.g.

         name(product,[112,114,111,100,117,99,116])


     i.e.  name(product,"product").


If X is instantiated to a variable, L must be instantiated  to  a  list  of

ASCII character codes.  E.g.

    | ?- name(X,[104,101,108,108,111])).

    X = hello

    | ?- name(X,"hello").

    X = hello



call(X)

     If X is a nonvariable term in the program text, then  it  is  executed

     exactly as if X appeared in the program text instead of call(X), e.g.

          ..., p(a), call( (q(X), r(Y)) ), s(X), ...


     is equivalent to

          ..., p(a), q(X), r(Y), s(X), ...


     However, if X is a variable in the program text, then if at runtime  X

     is  instantiated  to a term which would be acceptable as the body of a

     clause, the goal call(X) is executed as if that term  appeared  textu-

     ally  in place of the call(X), except that any  cut (`!') occurring in

     X will remove only those choice points in X.  If  X  is  not   instan-

     tiated   as  described  above,  an  error  message is printed and call

     fails.




                                    39












X    (where X is a variable) Exactly the  same  as  call(X).   However,  we

     prefer  the explicit usage of call/1 as good programming practice, and

     the use of a top level variable subgoal elicits  a  warning  from  the

     compiler.


conlength(C,L)


     Succeeds if the length of the print name of the constant C (which  can

     be an atom, buffer or integer), in bytes, is L.  If C is a buffer (see

     Section 5.8), it is the length of the buffer; if C is an  integer,  it

     is the length of the decimal representation of that integer, i.e., the

     number of bytes that a $writename will use.


5.6.  Sets




     When  there  are  many solutions to a  problem,  and  when  all  those

solutions  are  required   to   be   collected   together,   this   can  be

achieved  by  repeatedly backtracking  and gradually building up a list  of

the solutions.  The following evaluable predicates are provided to automate

this process.


setof(X,P,S)

     Read this as "S is the set of all instances of X   such   that  P   is

     provable''.   If  P  is  not  provable,  setof(X,P,S)  succeeds with S

     instantiated to the empty list [].  The term P  specifies  a  goal  or

     goals  as  in  call(P). S is a set of terms represented as  a list  of

     those terms, without duplicates, in the standard order for terms  (see



                                    40












     Section  5.7). If there are uninstantiated variables in P which do not

     also appear in X, then a  call  to  this   evaluable   predicate   may

     backtrack,  generating   alternative  values  for  S  corresponding to

     different instantiations of the free variables of P.  Variables occur-

     ring  in  P  will  not be treated as free if they are explicitly bound

     within P by an existential quantifier.  An existential  quantification

     is written:

         Y^Q


     meaning "there exists a Y such that Q is true", where  Y is some  Pro-

     log term (usually, a variable, or tuple or list of variables).


bagof(X,P,Bag)

     This is the same as setof except that the list (or alternative  lists)

     returned  will not be ordered,  and  may  contain duplicates.  If P is

     unsatisfiable, bagof succeeds binding Bag  to  the  empty  list.   The

     effect  of  this  relaxation is to save considerable time and space in

     execution.


findall(X,P,L)

     Similar to bagof/3, except that variables in P that do not occur in  X

     are  treated as local, and alternative lists are not returned for dif-

     ferent bindings of such variables.  The list L is, in  general,  unor-

     dered,  and  may  contain  duplicates.  If P is unsatisfiable, findall

     succeeds binding S to the empty list.


X^P




                                    41












     The system recognises this as meaning "there exists an X  such that  P

     is  true",  and  treats  it as equivalent to call(P).  The use of this

     explicit existential quantifier outside the setof and bagof constructs

     is superfluous.


5.7.  Comparison of Terms




     These  evaluable  predicates  are  meta-logical.    They  treat  unin-

stantiated  variables  as  objects  with  values  which  may  be  compared,

and  they  never instantiate those variables.  They should not be used when

what you really want is arithmetic comparison (Section 5.2) or unification.


     The  predicates  make reference to a standard total ordering of terms,

which is as follows:


     variables, in a standard order (roughly, oldest first - the order   is

     not related to the names of variables);


     numbers, from -"infinity" to +"infinity";


     atoms, in alphabetical (i.e. ASCII) order;


     complex  terms, ordered first by arity, then by the name of  principal

     functor, then by the arguments (in left-to-right order).


     For example, here is a list of terms in the standard order:

    [ X, -9, 1, fie, foe, fum, X = Y, fie(0,2), fie(1,1) ]


These are the basic predicates for comparison of arbitrary terms:



                                    42












X == Y


     Tests if the terms currently instantiating X  and   Y  are   literally

     identical   (in  particular,  variables in equivalent positions in the

     two terms must be identical).  For example, the question

         | ?- X == Y.


     fails (answers "no") because X and  Y  are   distinct   uninstantiated

     variables.  However, the question

         | ?- X = Y, X == Y.


     succeeds because the first goal unifies the two  variables  (see  page

     42).


X \== Y


     Tests  if  the  terms  currently  instantiating  X  and   Y   are  not

     literally identical.


T1 @< T2


     Term T1 is before term T2 in the standard order.


T1 @> T2


     Term T1 is after term T2 in the standard order.


T1 @=< T2


     Term T1 is not after term T2 in the standard order.





                                    43












T1 @>= T2


     Term T1 is not before term T2 in the standard order.




Some further predicates involving comparison of terms are:


compare(Op,T1,T2)


     The  result  of comparing terms T1 and T2 is Op,  where  the  possible

     values for Op are:

         `='   if T1 is identical to T2,

         `<'   if T1 is before T2 in the standard order,

         `>'   if T1 is after T2 in the standard order.


     Thus compare(=,T1,T2) is equivalent to T1 == T2.


sort(L1,L2)


     The elements of the list L1 are sorted into the  standard  order,  and

     any  identical  (i.e.  `==') elements are merged,  yielding  the  list

     L2.


5.8.  Buffers




     SB-Prolog supports the concept of buffers.  A  buffer  is  actually  a

constant and the characters that make up the buffer is the name of the con-

stant.  However, the symbol table entry for a buffer is not hashed and thus

is  not  added  to the obj-list, so two different buffers will never unify.



                                    44












Buffers can be allocated either in permanent space or on the heap.  Buffers

in  permanent space stay there forever; buffers on the heap are deallocated

when the ``allocate buffer'' goal is backtracked over.


     A buffer allocated on the heap can either be a simple  buffer,  or  it

can  be  allocated as a subbuffer of another buffer already on the heap.  A

subbuffer will be deallocated when its superbuffer is deallocated.


     There are occasions when it is not known, in advance, exactly how much

space  will be required and so how big a buffer should be allocated.  Some-

times this problem can be overcome by allocating a large buffer  and  then,

after  using  as much as is needed, returning the rest of the buffer to the

system. This can be done, but only  under  very  limited  circumstances:  a

buffer  is  allocated  from  the end of the permanent space, the top of the

heap, or from the next available space in the superbuffer; if no more space

has  been  used  beyond the end of the buffer, a tail portion of the buffer

can be returned to the system. This operation is  called  ``trimming''  the

buffer.


     The following is a list of library predicates  for  buffer  management

(predicates whose names begin with `$' are low-level routines intended only

for serious hackers willing to put up with little or no protection):




alloc_perm(Size, Buff)

     Allocates a buffer with a length Size in the permanent (i.e.  program)

     area.  Size must be bound to a number. On successful return, Buff will

     be bound to the allocated buffer.  The buffer, being in the  permanent


                                    45












     area, is never de-allocated.


alloc_heap(Size, Buff)

     Allocates a buffer of size Size on the heap  and  binds  Buff  to  it.

     Since it is on the heap, it will be deallocated on backtracking.


$alloc_buff(Size,Buff,Type,Supbuff,Retcode)


     Allocates a buffer.  Size is the length (in bytes) of  the  buffer  to

     allocate;  Buff  is the buffer allocated, and should be unbound at the

     time of the call; Type indicates where to allocate the buffer: a value

     of  0 indicates that the buffer is to be allocated in permanent space,

     1 that it should be on the heap, and 2 indicates  that  it  should  be

     allocated  from a larger heap buffer; Supbuff is the larger  buffer to

     allocate a subbuffer out of, and is only looked at  if  the  value  of

     Type is 2; Retcode is the return code: a value of 0 indicates that the

     buffer has been allocated, while a  value  of  1  indicates  that  the

     buffer  could  not  be  allocated due to lack of space.  The arguments

     Size, Type, and Supbuff (if Type = 2) are input arguments, and  should

     be  bound  at  the time of the call; Buff and Retcode are output argu-

     ments, and should be unbound at the time of the call.


trimbuff(Type, Buff, Newlen)

     This allows (in some very restricted circumstances)  the  changing  of

     the  size  of a buffer. Type is 0 if the buffer is permanent, 1 if the

     buffer is on the heap. Buff is the buffer.  Newlen is an integer:  the

     size  (which should be smaller than the original length of the buffer)

     to make the buffer. If the buffer is at the top of the heap  (if  heap


                                    46












     buffer)  or  the end of the program area (if permanent) then the heap-

     top (or program area top) will be readjusted down.  The length of  the

     buffer  will  be  modified to Newlen.  This is (obviously) a very low-

     level primitive and is for hackers only to implement grungy stuff.


$trim_buff(Size,Buff,Type,Supbuff)


     Trims the buffer Buff (possibly contained in superbuffer  Supbuff)  of

     type  Type to Size bytes. The value of Type indicates where the buffer

     is located: a value of 0 denotes a buffer in permanent space, a  value

     of  1  a  buffer on the heap, and a value of 2 a buffer within another

     buffer (the superbuffer).  All the arguments are input arguments,  and

     should  be  instantiated at the time of call (with the possible excep-

     tion of Supbuff, which is looked at only if Type is 2).  The  internal

     length of the buffer Buff is changed to Size.


conlength(Constant,Length)


     Succeeds if the length of the print  name  of  the  constant  Constant

     (which  can  be  an atom, buffer or integer), in bytes, is Length.  If

     Constant is a buffer, it is the length of the buffer; if  Constant  is

     an  integer,  it  is  the length of the decimal representation of that

     integer, i.e., the number of bytes that a $writename will use.


5.9.  Modification of the Program




     The predicates defined in this section allow modification of the  pro-

gram  as  it  is  actually  running.   Clauses  can be added to the program


                                    47












(asserted) or removed from the program (retracted).  At the  lowest  level,

the  system  supports the asserting of clauses with upto one literal in the

body.  It does this by allocating a  buffer  and  compiling  code  for  the

clause  into  that  buffer.  Such a buffer is called a ``clause reference''

(clref).  The clref is then added to a  chain  of  clrefs.   The  chain  of

clrefs  has  a  header, which is a small buffer called a ``predicate refer-

ence'' (prref), which contains pointers to the beginning  and  end  of  its

(prref),  which  contains pointers to the beginning and end of its chain of

clrefs.  Clause references are quite similar to ``database references''  of

C-Prolog, and can be called.


     A prref is normally associated with a predicate  symbol  and  contains

the  clauses  that have been asserted for that symbol.  However, prrefs can

be constructed and clrefs added to them, and such clauses can  be  can   be

constructed  and  clrefs added to them, and such clauses can be called, all

without associating that prref with any  particular  predicate  symbol.   A

predicate  symbol  that   has  an  associated prref is called a ``dynamic''

predicate (other  predicate types are ``compiled'' and ``undefined'').


     There are options as to where clrefs are  allocated and  how they  are

linked  to  a  chain  of   clrefs  associated  with a  prref.   A clref can

either be allocated in permanent space (the normal  arrangement)  or  as  a

sub-buffer  of  a superbuffer on the heap.  When adding a  clref to a prref

chain, it can be be added at the beginning  of the  chain or at the end  of

the  chain.   In  addition,  one  of  the argument positions can be used to

index, so that subsequent retrievals will try  to index on that position.




                                    48












assert(C)


     The current instance of C is interpreted as a clause and is  added  to

     the  program  (with new private variables replacing any uninstantiated

     variables), at the end of the list of clauses for that  predicate.   C

     must be instantiated to a non-variable.


assert(C, Opts)


     As for assert/1, with Opts a list of options.  The  options  currently

     recognized are:


   first


     If on, causes the asserted clause to be added as the first  clause  of

     the database.  Default: off.


   index


     If on, causes an index to be generated on the first  argument  of  the

     clause.  Default: off.


   index(N)


     If on, causes an index to be generated on the N[th]  argument  of  the

     clause.  Default: off.


   q


     ``quick''.  If on, invokes an assertion algorithm that is simpler  and

     more efficient than the general one.  However, the code generated with



                                    49












     the simpler algorithm may not be correct if there are  repeated  vari-

     ables within compound terms in the body of the clause, e.g. in

                 p(X) :- q([X, X]).


     Default: off.


asserti(C,N)


     The current instance of C, interpreted as a clause, is asserted to the

     program  with  an index on its N[th] argument.  If N is zero, no index

     is created.


asserta(C)


     Similar to assert(C), except that the new  clause  becomes  the  first

     clause of the procedure concerned.


asserta(C, Ref)


     Similar to asserta(C), but also unifies Ref with the clause  reference

     of the clause asserted.


assertz(C)


     Similar to assert(C), except that the  new  clause  becomes  the  last

     clause of the procedure concerned.


assertz(C, Ref)


     Similar to assertz(C), but also unifies Ref with the clause  reference

     of the clause asserted.



                                    50












assert_union(P, Q)


     The clauses for Q are added to the clauses for P.   For  example,  the

     call

                 | ?- assert_union(p(X,Y),q(X,Y)).


     has the effect of adding the rule

         p(X,Y) :- q(X,Y).


     as the last rule defining p/2.  If P is not defined, it results in the

     call to Q being the only clause for P.



     The variables in the arguments to $assert_union/2 are not significant,

     e.g. the above would have been equivalent to

                 | ?- assert_union(p(Y,X),q(X,Y)).
         or
                 | ?- assert_union(p(_,_),q(_,_)).


     However, the arities of the two predicates involved must  match,  e.g.

     even though the goal

                 | ?- assert_union(p(X,Y), r(X,Y,Z)).


     will succeed, the predicate p/2 will not in  any  way  depend  on  the

     clauses for r/3.


$assert(Clause,AZ,Index,Clref)


     Asserts a clause to a predicate.  Clause is the clause to assert.   AZ

     is  0  for  insertion as the first clause, 1 for insertion as the last

     clause.  Index is the number of the argument on which to  index (0 for



                                    51












     no indexing).  Clref is returned  as the  clause reference of the fact

     newly asserted.  If  the  main  functor  symbol  of  Clause  has  been

     declared (by $assertf_alloc_t/2, see below) to have its clauses on the

     heap, the clref will be allocated there. If the  predicate  symbol  of

     Clause  is  undefined, it will be initialized and Clause added. If the

     predicate symbol has compiled clauses, it is  first  converted  to  be

     dynamic  (see  symtype/2, Section 5.10) by adding a special clref that

     calls the compiled clauses.  Fact, AZ and Index are  input  arguments,

     and  should  be  instantiated  at the time of call; Clref is an output

     argument, and should be uninstantiated at the time of call.


$assertf_alloc_t(Palist,Size)


     Declares that each predicate in the  list  Palist  of  predicate/arity

     pairs  (terms of the form `/'(P,N) where P is a predicate symbol and N

     the arity of P) is to have any facts asserted  to  them  stored  in  a

     buffer  on  the  heap,  to be allocated here.  This allocates a super-

     buffer of size Size on the heap.  Future assertions  to  these  predi-

     cates  will  have their clauses put in this buffer.  When this call is

     backtracked over, any clauses asserted to these predicates are deallo-

     cated, and a subsequent call to any of those predicates will cause the

     simulator to report an error and fail.  Both Palist and Size are input

     arguments, and should be instantiated at the time of call.


retract(Head)


     The first clause in the program whose head  matches  Head  is  erased.

     This  predicate  may  be  used in a non-deterministic fashion, i.e. it


                                    52












     will successively backtrack to retract clauses whose heads match Head.

     Head  must be initially instantiated to a non-variable. In the current

     implementation, retract  works  only  for  asserted  (e.g.  consulted)

     clauses.


abolish(P)


     Completely remove all clauses for the procedure  with  head  P  (which

     should be a term). For example, the goal

         | ?- abolish( p(_, _, _) ).


     removes all clauses for the predicate p/3.


abolish(P, N)


     Completely remove all clauses for the predicate P (which should be  an

     atom) with arity N (which should be an integer).


call_ref(Call, Ref)


     Calls the predicate whose database reference (prref) is Ref, using the

     literal Call as the call.  This is similar to call_ref(Call, Ref, 0).


call_ref(Call, Ref, Tr)


     Calls the predicate whose database reference (prref) is Ref, using the

     literal  Call  as the call.  Tr must be either 0 or 1: if Tr is 0 then

     the call Call is made assuming  the  ``trust''  optimization  will  be

     made;  if Tr is 1 then the ``trust'' optimization is not used, so that

     any new fact added before final failure will be seen by Call.   (Also,



                                    53












     this currently does not take advantage of any indexing that might have

     been constructed.  Call, Ref and  Tr  are  all  input  arguments,  and

     should be instantiated at the time of call.




The basic library predicates that support the manipulation  of  prrefs  and

clrefs are as follows:


$db_new_prref(Prref,Where,Supbuff)


     Creates an empty Prref, i.e. one with no facts in it.  If  called,  it

     will  simply  fail.   Where  indicates where the prref should be allo-

     cated:  a value of 0 indicates the permanent area, while a value of  2

     indicates  that  it is to be allocated as a subbuffer.  Supbuff is the

     superbuffer from which to allocate Prref if Where is 2.  Where  should

     be  instantiated  at the time of call, while Prref should be uninstan-

     tiated; in addition, if Where is 2, Supbuff should be instantiated  at

     the time of call.


$db_assert_fact(Fact,Prref,AZ,Index,Clref,Where,Supbuff)


     Fact is a fact to be asserted; Prref is a predicate reference to which

     to  add  the asserted fact; AZ is either 0, indicating the fact should

     be inserted as the first clause in Prref, or 1, indicating  it  should

     be  inserted  as the last; Index is 0 if no index is to be built, or n

     if an index on the n[th] argument of the fact is to be used.  (Assert-

     ing at the beginning of the chain with indexing is not yet supported.)

     Where indicates where the clref is to  be  allocated:  a  value  of  0



                                    54












     indicates  that it should be in the permanent area, while a value of 2

     indicates that it should be  allocated  as  a  subbuffer  of  Supbuff.

     Clref  is returned and it  is  the  clause reference  of the  asserted

     fact.   Fact, Prref, AZ, Index and  Where  are  input  arguments,  and

     should  be  instantiated at the time of call; in addition, if Where is

     2, then Supbuff should also be instantiated.  Clref is an output argu-

     ment, and should be uninstantiated at the time of call.


$db_add_clref(Fact,Prref,AZ,Index,Clref,Where,Supbuff)


     Adds the clref Clref to the prref Prref. Fact is  the  fact  that  has

     been  compiled  into  Clref (used only to get the arity and for index-

     ing).  The other parameters are as for $db_assert_fact/7.


$db_call_prref(Call,Prref)


     Calls the prref Prref using the literal Call as the call.  The call is

     done  by  simply  branching  to  the first clause.  New facts added to

     Prref after the last fact has been retrieved by Call, but before  Call

     is  failed  through,  will not be used.  Both Call and Prref are input

     arguments, and should be instantiated at the time of call.


$db_call_prref_s(Call,Prref)


     This also  calls the prref Prref using Call as the call.  The  differ-

     ence  from  $db_call_prref  is  that  this  does not use the ``trust''

     optimization, so that any new fact added before final failure will  be

     seen  by  Call.   (Also, this currently does not take advantage of any

     indexing that might have been constructed, while $db_call_prref does.)


                                    55












     Both Call and Prref are input arguments, and should be instantiated at

     the time of call.


$db_get_clauses(Prref,Clref,Dir)


     This returns, nondeterministically, all the  clause  references  Clref

     for  clauses  asserted  to  prref  Prref.  If Dir is 0, then the first

     clref on the list is returned first;  if  Dir  is  1,  then  they  are

     returned  in  reverse  order.   Prref and Dir are input arguments, and

     should be instantiated at the time of call; Clref is an  output  argu-

     ment, and should be uninstantiated at the time of call.


$db_kill_clause(Clref)


     This predicate retracts the fact referenced by clref Clref.   It  does

     this  by  simply  making  the  first  instruction of the clause a fail

     instruction.  This means that this clause will  fail  whenever  it  is

     called  in  the future, no matter how it is accessed.  Clref should be

     instantiated at the time of call.


5.10.  Environmental




op(priority, type, name)


     Treat name as an operator of the stated type and priority (see Section

     3.2).   name  may  also  be  a  list  of names, in which all are to be

     treated as operators of the stated type and priority.





                                    56












break


     Causes the current execution to be suspended  at  the  next  procedure

     call.   Then  the  message  ``[ Break (level 1) ]'' is displayed.  The

     interpreter is then ready to accept input as though it was at the  top

     level  (except  that  at break level n > 0, the prompt is ``n: ?- '').

     If another call of break is encountered, it moves up to level  2,  and

     so  on.   To  close  the  break  and  resume  the  execution which was

     suspended, type the END-OF-INPUT character.  Execution will be resumed

     at the procedure call where it had been suspended.  Alternatively, the

     suspended execution can be aborted by calling the evaluable  predicate

     abort, which causes a return to the top level.


abort


     Aborts the current execution, taking you back to top level.


save(F)


     The system saves the current state of the system into file F.


restore(F)


     The system restores the saved state in file F to be the current state.

     One  restriction  imposed by the current system is that various system

     parameters (e.g. stack sizes, permanent space, heap  space,  etc.)  of

     the saved state have to be the same as that of the current invocation.

     Thus, it is not possible to save a  state  from  an  invocation  where

     50000  words  of  permanent space had been allocated, and then restore



                                    57












     the same state in an invocation with 100000 words of permanent space.


cputime(X)


     Unifies X with the time elapsed, in milliseconds, since the system was

     started up.


$getenv(Var,Val)


     Val is unified with the value of the Unix  environment  variable  Var.

     Fails is Var is undefined.


statistics


     Prints out the current allocations and amounts of space used for  each

     of  the four main areas: the permanent area, the local stack, the glo-

     bal stack and the trail stack.  Does not work well unless the  simula-

     tor has been called with the -s option (see Section 7.2).


nodynload(P, N)


     Flags the predicate P with arity N as one that should not be attempted

     to  be  dynamically  loaded  if  it  is  undefined.  If a predicate so

     flagged is undefined when a call to it is encountered, the call  fails

     quietly without trying to invoke the dynamic loader or giving an error

     message.  P and N should be instantiated to an atom  and  an  integer,

     respectively, at the time of call to nodynload/2.


symtype(T,N)





                                    58












     Unifies N with the ``internal type'' of the principal functor  of  the

     term  T,  which  must  be  instantiated at the time of the call.  N is

     bound to 0 if T does not have an entry point defined (i.e.  cannot  be

     executed); to 1 if the principal functor of T is ``dynamic'', i.e. has

     asserted code; to 2 if the principal  functor  for  T  is  a  compiled

     predicate;  and  3  if  T denotes a buffer.  Thus, for example, if the

     predicate p/2 is a compiled predicate which has been loaded  into  the

     system, the goal

                 | ?- symtype(p(_,_), X).


     will succeed binding X to 2; on the other hand, the goal

                 | ?- assert(q(a,b,c)), symtype(q(_,_,_), X).


     will succeed binding X to 1.


system(Call)


     Calls the operating system with the atom Call as argument.  For  exam-

     ple, the call

         | ?- system('ls').


     will produce a directory listing.  Since system/1 is executed by fork-

     ing off a shell process, it cannot be used, for example, to change the

     working directory of the simulator.


syscall(N,Args,Res)


     Executes the Unix system  call  number  N  with  arguments  Args,  and

     returns  the result in Res. N is an integer, and Args a Prolog list of



                                    59












     the arguments to the system call.  For example, to execute the  system

     call  ``creat(File,Mode)'',  knowing  that  the syscall number for the

     Unix command creat(2) is 8, we execute the goal

         | ?- syscall(8, [File, Mode], Des).


     where Des is the file  descriptor  returned  by  creat.   The  syscall

     numbers for some Unix system calls are given in Table 2.


5.11.  Global Values




     SB-Prolog has some primitives that permit the programmer to manipulate

global  values.   These  are  provided primarily as an efficiency hack, and

needless to say, should be used with a great deal of care.


_________________________________________________________________________
    exit                      1     |       fork                     2   |
    read                      3     |       write                    4   |
    open                      5     |       close                    6   |
    creat                     8     |       link                     9   |
    unlink                   10     |       chdir                   12   |
    chmod                    15     |       lseek                   19   |
    access                   33     |       kill                    37   |
    wait                     84     |       socket                  97   |
    connect                  98     |       accept                  99   |
    send                    101     |       recv                   102   |
    bind                    104     |       setsockopt             105   |
    listen                  106     |       recvmsg                113   |
    sendmsg                 114     |       getsockopt             118   |
    recvfrom                125     |       sendto                 133   |
    socketpair              135     |       mkdir                  136   |
    rmdir                   137     |       getsockname            150   |
____________________________________|____________________________________|


           Table 2: Some Syscall Numbers for Unix Systems Calls






                                    60












globalset(Term)


     Allows the user to save a global value.  Term must be bound to a  com-

     pound  term, say p(V). V must be a number or a constant or a variable.

     If V is a number or a constant, the effect of globalset(p(V))  can  be

     described as:

         retract(p(_)), assert(p(V)).


     I.e., p is a predicate that when called will, from now on (until  some

     other  change  by globalset/1), deterministically return V.  If V is a

     variable, the effect is to make V a global  variable  whose  value  is

     accessible  by  calling  p. For example, executing ``globalset(p(X))''

     makes X a global variable. X can be set by unification with some other

     term.  On backtracking, X will be restored to its earlier value.


gennum(Newnum)


     gennum/1 sets its argument to a new integer every time it is invoked.


gensym(C,Newsym)


     gensym/2 sets its second argument to an atom whose  name  is  made  by

     concatenating  the  name  of  the atom C to the current gennum number.

     This new constant is bound to Newsym.  For  example,  if  the  current

     gennum number is 37, then the call

         | ?- gensym(aaa,X)


     will succeed binding X to the atom `aaa37'.





                                    61












6.  Debugging




6.1.  High Level Tracing




     The preferred method of tracing execution  is  through  the  predicate

trace/1.   This predicate takes as argument a term P/N, where P is a predi-

cate name and N its arity, and sets a ``trace point'' on the  corresponding

predicate; it can also be given a list of such terms, in which case a trace

point is set on each member of the list.  For example, executing

            | ?- trace(pred1/2), trace([pred2/3, pred3/2]).


sets trace points on predicates pred1/2, pred2/3 and pred3/2.   Only  those

predicates are traced that have trace points set on them.


     If all the predicates in a file are to be traced, it is  usually  con-

venient to use the PredList parameter of compile/4 or consult/3, e.g.:

            | ?- compile(foo, 'foo.out', [t,v], Preds), load('foo.out'), trace(Preds).
    or
            | ?- consult(foo, [v], Preds), trace(Preds).


Notice that in the first case, the t  compiler  option  (see  Section  8.3)

should  be  specified  in order to turn off certain assembler optimizations

and facilitate tracing.  In  the  second  case,  the  same  effect  may  be

achieved by specifying the t option to consult.


     The trace points set on predicates may be overwritten by loading  byte

code  files  via load/1, and in this case it may be necessary to explicitly

set trace points again on the loaded predicates.  This does not happen with


                                    62












consult:  predicates  that  were being traced continue to have trace points

set after consulting.


     The tracing facilities of SB-Prolog are in many ways very  similar  to

those  of  C-Prolog.   However,  leashing  is not supported, and only those

predicates can be traced which have had trace points set  on  them  through

trace/1.   This  makes  trace/1  and spy/1 very similar: essentially, trace

amounts to two levels of spy points.  In SB-Prolog, tracing occurs at  Call

(i.e.  entry to a predicate), successful Exit from a clause, and Failure of

the entire call.  The tracing options available during  debugging  are  the

following:


c, NEWLINE: Creep

     Causes the system to single-step to the next  port  (i.e.  either  the

     entry to a traced predicate called by the executed clause, or the suc-

     cess or failure exit from that clause).


a: Abort

     Causes execution to abort and control  to  return  to  the  top  level

     interpreter.


b: Break

     Calls the evaluable predicate break, thus invoking recursively  a  new

     incarnation  of  the  system interpreter.  The command prompt at break

     level n is

                 n: ?-


     The user may return to the previous break level by entering the system



                                    63












     end-of-file   character   (e.g.   ctrl-D),   or  typing  in  the  atom

     end_of_file; or to the top level interpreter by typing in abort.


f: Fail

     Causes execution to fail, thus transferring control to the  Fail  port

     of the current execution.


h: Help

     Displays the table of debugging options.


l: Leap

     Causes the system to resume running the program, only stopping when  a

     spy-point  is reached or the program terminates.  This allows the user

     to follow the execution at a higher level than exhaustive tracing.


n: Nodebug

     Turns off debug mode.


q: Quasi-skip

     This is like Skip except that it does not mask out spy points.


r: Retry (fail)

     Transfers to the Call port of the current goal.  Note,  however,  that

     side effects, such as database modifications etc., are not undone.


s: Skip

     Causes tracing to be turned off for the entire execution of  the  pro-

     cedure.   Thus,  nothing is seen until control comes back to that pro-

     cedure, either at the Success or the Failure port.



                                    64












Other predicates that are useful in debugging are:




untrace(Preds)

     where Preds is a term P/N, where P is  a  predicate  name  and  N  its

     arity,  or  a  list of such terms.  Turns off tracing on the specified

     predicates.  Preds must be instantiated at the time of the call.


spy(Preds)

     where Preds is a term P/N, where P is  a  predicate  name  and  N  its

     arity,  or  a  list  of  such terms.  Sets spy points on the specified

     predicates.  Preds must be instantiated at the time of the call.


nospy(Preds)

     where Preds is a term P/N, where P is  a  predicate  name  and  N  its

     arity,  or  a list of such terms.  Removes spy points on the specified

     predicates.  Preds must be instantiated at the time of the call.


debug

     Turns on debugging mode.  This causes subsequent execution  of  predi-

     cates  with  trace or spy points to be traced, and is a no-op if there

     are no such predicates.  The predicates trace/1 and spy/1 cause debug-

     ging mode to be turned on automatically.


nodebug

     Turns off debugging mode.  This causes trace  and  spy  points  to  be

     ignored.





                                    65












debugging

     Displays information about whether debug mode is on or not, and  lists

     predicates that have trace points or spy points set on them.


tracepreds(L)

     Binds L to a list of terms P/N where the predicate P of arity N has  a

     trace point set on it.


spypreds(L)

     Binds L to a list of terms P/N where the predicate P of arity N has  a

     spy point set on it.




     There is one known bug in the package: attempts to set  trace  points,

via  trace/1,  on  system and library predicates that are used by the trace

package can cause bizarre behaviour.


6.2.  Low Level Tracing




     SB-Prolog also provides a facility for low level tracing of execution.

This  can  be  activated  by  invoking the simulator with the -T option, or

through the predicate trace/0.  It causes trace information to  be  printed

out at every call (including those to system trap handlers).  The volume of

such trace information can very become large very quickly, so  this  method

of tracing is not recommended in general.


     Low level tracing may be turned off using the predicate untrace/0.




                                    66












7.  The Simulator




     The simulator resides in the SB-Prolog system directory sim.  The fol-

lowing sections describe various aspects of the simulator.


7.1.  Invoking the Simulator




     The simulator is invoked by the command



            sbprolog bc_file




where bc_file is a byte code file resulting from the compilation of a  Pro-

log  program.  In almost all cases, the user will wish to interact with the

SB-Prolog query evaluator, in which case bc_file will be $readloop, and the

command will be



            sbprolog PATH/\\$eadloop




where PATH is the path to the directory containing the command  interpreter

$readloop.  This directory, typically, is the system directory modlib.


     The command interpreter reads in a query typed in by the user,  evalu-

ates  it  and  prints  the answer(s), repeating this until it encounters an

end-of-file (the standard end-of-file character on the system,  e.g.  ctrl-

D), or the user types in end_of_file or halt.


                                    67












     The user should ensure that the the directory containing  the  execut-

able  file  sim  (typically,  the  system directory sim) is included in the

shell variable path; if not, the full path to the simulator will have to be

specified.


     In general, the simulator may be invoked with a variety of options, as

follows:



            sbprolog -options bc_file
    or
            sbprolog -option<1> -option<2> ... -option<n> bc_file




The options recognized by the simulator are described below.


     When called with a byte code file bc_file, the simulator begins execu-

tion  with the first clause in that file.  The first clause in such a file,

therefore, should be a clause without any arguments in the head (otherwise,

the  simulator  will  attempt  to dereference argument pointers in the head

that are really pointing into deep space, and usually come to a  sad  end).

If  the  user is executing a file in this manner rather than using the com-

mand interpreter, he should also be careful to include the undefined predi-

cate  handler  `_$undefined_pred'/1,  which is normally defined in the file

modlib/$init_sys.P.


7.2.  Simulator Options








                                    68












The following is a list of options recognized by the simulator.


T    Generates a trace at entry to each called routine.


d    Produces a disassembled dump of bc_file into a file  named  `dump.pil'

     and exits.


n    Adds machine addresses when producing trace and dump.


s    Maintains information for the builtin statistics/0.  Default: off.


m size

     Allocates size words (4 bytes) of space to the local  stack  and  heap

     together.  Default: 100000.


p size

     Allocates size words of space to the program area.  Default: 100000.


b size

     Allocates size words of space to the trail stack.  Default: m/5, where

     m  is  the  amount  of  space  allocated  to  the local stack and heap

     together.  This parameter, if specified, must follow the -m parameter.




As an example, the command

            sim -s -p 60000 -m 150000 \$readloop


starts the simulator executing the command interpreter with 60000 bytes  of

program  space,  150000  bytes  of  local  and  global  stack space and (by

default) 30000 bytes of trail stack space; the s  option  also  results  in



                                    69












statistics information being maintained.


7.3.  Interrupt Handling




     SB-Prolog provides a  facility  for  exception  handling  using  user-

definable  interrupt  handlers.   This can be used both for external inter-

rupts, e.g. those generated from the keyboard by the user or  from  signals

other  processes;  or internal traps, e.g. those caused by stack overflows,

encountering undefined  predicates,  etc.   For  example,  the  ``undefined

predicate''   interrupt   is   handled,   by   default,  by  the  predicate

`_$undefined_pred'/1, which is defined in the file modlib/$init_sys.P.  The

default  action  on  encountering  an  undefined predicate is to attempt to

dynamically load a file whose name matches that of the undefined predicate.

However,  the  user may easily alter this behaviour by redefining the unde-

fined predicate handler.


8.  The Compiler




The compiler translates Prolog source files into  byte-code  object  files.

It  is  written  entirely in Prolog.  The byte code for the compiler can be

found in the SB-Prolog  system  directory  cmplib,  with  the  source  code

resident in cmplib/src.


     Byte code files may be concatenated together  to  produce  other  byte

code  files.   Thus,  for  example,  if  foo1  and foo2 are byte code files

resulting from the compilation of two Prolog source programs, then the file



                                    70












foo, obtained by executing the shell command

            cat foo1 foo2 > foo


is a byte code file as well, and may be loaded and executed.  In this case,

loading  and  executing  the file foo would give the same result as loading

foo1 and foo2 separately, which in turn would be the same as  concatenating

the  original  source  files and compiling this larger file.  This makes it

easier to compile large programs: one need only  break  them  into  smaller

pieces,  compile  the  individual  pieces,  and  concatenate the byte files

together.


     The following sections describe the various aspects of the compiler in

more detail.


8.1.  Structure of the Compiler




The compilation of a Prolog program proceeds in four phases.  In the  first

phase,  the  source  program is read in and  passed through a preprocessor.

The output of the preprocessor is essentially another  Prolog  source  pro-

gram.   Next,  this  program is transformed into an internal representation

(essentially an annotated abstract syntax tree).  The third phase  involves

generating  WAM  ``assembly'' code and peephole optimization.  Finally, the

WAM assembly code is processed by an assembler which generates byte code.


8.2.  Invoking the Compiler







                                    71












The compiler is invoked through the Prolog predicate compile:

            | ?- compile(InFile [, OutFile ] [, OptionsList ]).


where optional parameters are enclosed in brackets.  InFile is the name  of

the  input (i.e. source) file; OutFile is the name of the output file (i.e.

byte code) file; OptionsList is a list of compiler options (see below).


     The input and output file names must  be  Prolog  atoms,  i.e.  either

begin  with  a  lower  case  letter or dollar sign `$', and consist only of

letters, digits, and underscores; or, be enclosed within single quotes.  If

the output file name is not specified, it defaults to InFile.out.  The list

of options, if specified, is a Prolog list, i.e. a term of the form

            [ option<1>, option<2>, ..., option<n> ].


If left unspecified, it defaults to the empty list [].


     In fact, the output file name and the options list may be specified in

any order.  Thus, for example, the queries

            | ?- compile('/usr/debray/foo', foo_out, [v]).
    and
            | ?- compile('/usr/debray/foo', [v], foo_out).


are equivalent, and specify that the Prolog source  file  `/usr/debray/foo'

is  to  be  compiled  in verbose mode (see ``Compiler Options'' below), and

that the byte code is to be generated into the file foo_out.


     The compile predicate may also be called with a fourth parameter:

            | ?- compile(InFile, OutFile, OptionsList, PredList).


where InFile, OutFile and OptionsList  are  as  before;  compile/4  unifies



                                    72












PredList  with  a  list  of  terms  P/N  denoting the predicates defined in

InFile, where P is a predicate name and N its arity.  PredList,  if  speci-

fied,  is usually given as an uninstantiated variable; its principal use is

for setting trace points on the predicates in the  file  (see  Section  6),

e.g. by executing

            | ?- compile('/usr/debray/foo', foo_out, [v], L), load(foo_out), trace(L).


Notice that PredList can only appear in compile/4.


8.3.  Compiler Options




The following options are currently recognized by the compiler:


a    Specifies that an ``assembler'' file is to be created.   The  name  of

     the  assembler  file  is  obtained by appending ``.asl'' to the source

     file name.  While the writing out of assembly code slows down the com-

     pilation  process  to  some  extent,  it  allows the assembler to do a

     better job of optimizing away indirect subroutine linkages  (since  in

     this  case  the  assembler has assembly code for the entire program to

     work with at once, not just a single predicate).  This results in code

     that is faster and more compact.


d    Dumps expanded macros to the user (see Section 10).


e    Expand macros (see Section 10).


i    Specifies that indexes are to be generated.  The pragma file (see Sec-

     tion 14) corresponding to the source file is consulted for information



                                    73












     regarding predicates which should have indexes  constructed,  and  the

     arguments on which indexes are to be constructed.


t    If  specified,  turns  off  assembler  optimizations  that   eliminate

     indirect  branches  through  the  symbol  table  in  favour  of direct

     branches.  This is useful in debugging compiled code.  It is necessary

     if the extension table feature is to be used.


v    If specified, compiles in  ``verbose''  mode,  which  causes  messages

     regarding progress of compilation to be printed out.


8.4.  A Note on Coding for Efficiency




     The SB-Prolog system tends to  favour  programs  that  are  relatively

pure.   Thus,  for example, asserts tend to be quite expensive, encouraging

the user to avoid them if possible.  This section points out some syntactic

constructs  that  lead  to the generation of efficient code.  These involve

(i) avoiding the creation of backtrack points;  and  (ii)  minimizing  data

movement  between  registers.  Optimization of logic programs is an area of

ongoing research, and we expect to enhance the capabilities of  the  system

further in future versions.


8.4.1.  Avoiding Creation of Backtrack Points




     Since the creation of backtrack points is relatively  expensive,  pro-

gram  efficiency  may  be  improved  substantially by using constructs that

avoid the creation of  backtrack  points  where  possible.   The  SB-Prolog


                                    74












compiler  recognizes  conditionals  involving  certain complementary inline

tests, and generates code that does  not  create  choice  points  for  such
                               _        _
cases.   Two  inline  tests  p(X) and q(X) are complementary if and only if
  _          _
p(X) = not(q(X)).  For example, the literals `X > Y' and `X =< Y' are  com-

plementary.  At this point, complementary tests are recognized as such only

if their argument tuples are identical.  The  inline  predicates  that  are

treated  in  this  manner, with their corresponding complementary literals,

are shown in Table 3.  The syntactic constructs recognized are:


(i)  Disjuncts of the form

                         _                      _
         head :- (( test(X), ... ) ; ( not(test(X)), ...)).


     or



                 _________________________________________
                |    Inline Test    |  Complementary Test |
                |___________________|_____________________|
                | >/2               |  =</2               |
                |___________________|_____________________|
                | =</2              |  >/2                |
                |___________________|_____________________|
                | >=/2              |  </2                |
                |___________________|_____________________|
                | </2               |  >=/2               |
                |___________________|_____________________|
                | =:=/2             |  =\=/2              |
                |___________________|_____________________|
                | =\=/2             |  =:=/2              |
                |___________________|_____________________|
                | var/1             |  nonvar/1           |
                |___________________|_____________________|
                | nonvar/1          |  var/1              |
                |___________________|_____________________|

          Table 3: Complementary tests recognized by the compiler





                                    75










                         _                       _
         head :- (( test(X), ... ) ; ( comp_test(X), ...)).


     where test is one  of  the  inline  tests  in  the  table  above,  and

     comp_test  the  corresponding  complementary test (note that the argu-

     ments to test and comp_test have to be identical).


(ii) Conditionals of the form

         head :- (test<1>, ... , test<n>) -> True_Case ; False_Case.


     or

         head :- (test<1>; ... ; test<n>) -> True_Case ; False_Case.


     where each test<i> is an inline test, as mentioned in the table above.


     The code generated for these cases involves  a  test  and  conditional

branch,  and  no choice point is created.  We expect future versions of the

translator to recognize a wider class of complementary tests.


     Notice that this discourages the use of explicit cuts.   For  example,

whereas a choice point will be created for

    part(M,[E|L],U1,U2) :-
       ((E =< M, !, U1 = [E|U1a], U2 = U2a) ;
        (U1 = U1a, U2 = [E|U2a])),
       part(M,L,U1a,U2a).


no choice point will be created for either

    part(M,[E|L],U1,U2) :-
       (E =< M ->
          (U1 = [E|U1a], U2 = U2a) ;
          (U1 = U1a, U2 = [E|U2a])),
       part(M,L,U1a,U2a).


or




                                    76











    part(M,[E|L],U1,U2) :-
       ((E =< M, U1 = [E|U1a], U2 = U2a) ;
        (E > M,  U1 = U1a, U2 = [E|U2a])),
       part(M,L,U1a,U2a).


Thus, either of the two later versions will be more efficient than the ver-

sion with the explicit cut.


8.4.2.  Minimizing Data Movement Between Registers




     Data movement between registers for parameter passing may be minimized

by  leaving  variables  in  the  same  argument position wherever possible.

Thus, the clause

            p(X,Y) :- p1(X,Y,0).


is preferable to

            p(X,Y) :- p1(0,X,Y).


because the first definition leaves the variables X and Y in the same argu-

ment  positions  (first and second, respectively), while the second defini-

tion does not.


8.5.  Assembly




     The SB-Prolog assembler can be invoked by  loading  the  compiler  and

using the predicate $asm/3:

            | ?- $asm(InFile, OutFile, OptionsList).


where InFile is a Prolog atom which is the name of a  WAM  assembly  source

file  (e.g.   the ``.asl'' file generated when a Prolog program is compiled


                                    77












with the ``a'' option), OutFile is  an  atom  which  is  the  name  of  the

intended byte code file, and OptionsList is a list of options.  The options

recognized by the assembler are:


v    ``Verbose'' mode.  Prints out information regarding progress of assem-

     bly.


t    ``Trace''.  If specified, the assembler generates code to  force  pro-

     cedure  calls  to  branch  indirectly via the symbol table, instead of

     using a direct branch.  This is Useful for tracing compiled code.   It

     is necessary if the extension table feature is to be used.


The assembler is intended primarily to support the compiler, so the  assem-

bly  language syntax is quirky in places.  The interested reader is advised

to look at the assembly files resulting from  compilation  with  the  ``a''

option for more on SB-Prolog assembler syntax.


9.  Modules




     To describe how modules (or maybe more properly, just  libraries)  are

currently  supported in our system, we must describe the _$undefined_pred/1

interrupt handler.  The system keeps a table of modules and  routines  that

are needed from each.  When a predicate is found to be undefined, the table

is searched to see if it is defined by some module.  If so, that module  is

loaded  (if  it  hasn't been previously loaded) and the association is made

between the routine name as defined in the module, and the routine name  as

used by the invoker.



                                    78












     The table of modules and needed routines is:

     defined_mods(Modname, [pred<1>/arity<1>, ..., pred<n>/arity<n>]).


where Modname is the name of the module.  The module  exports  n  predicate

definitions.  The first exported pred is of arity arity<>1, and needs to be

invoked by the name of pred<1>.


     The table of modules that have already been loaded is given by

            loaded_mods(Modname).


A module is a file of predicate definitions, together with a fact  defining

a  list  of predicates exported by that module, and a set of facts, each of

which specifies, for some other module, the predicates imported  from  that

module.   For  example,  consider  a  module name `p'. It contains a single

fact, named p_export, that is true of the list  of  predicate/arity's  that

are exported.  E.g.

            p_export([p1/2, p2/4])


indicates that the module p exports the predicates p1/2 and p2/4.  For each

module  m which contains predicates needed by the module p, there is a fact

for p_use, describing what module is needed and the names of the predicates

defined  there  that  are needed.  For example, if module p needs to import

predicates ip1/2 and ip2/3 from module q, there would be a fact

            p_use(q,[ip1/2, ip2/3])


where q is a module that exports two predicates: one 2-ary and  one  3-ary.

This list corresponds to the export list of module q.





                                    79












     The correspondence between the predicates in the  export  list  of  an

exporting  module,  and  those  in the import or use list of a module which

imports one or more of them, is by position, i.e. the  predicate  names  at

the  exporting  and  importing  names may be different, and the association

between names in the two lists is by the position  in  the  list.   If  the

importing  module  does  not  wish  to import one or more of the predicates

exported by the exporting module, it may put an anonymous variable  in  the

corresponding  position  in  its  use list.  Thus, for example, if module p

above had wished to import only the predicate  ip2/3  from  module  q,  the

corresponding use fact would be

            p_use(q, [_, ip2/3]).



     The initial set of predicates and the modules from which they  are  to

be  loaded is set up by an initial call to $prorc/0 (see the SB-Prolog sys-

tem file modlib/src/$prorc.P).  This predicate makes initial calls  to  the

predicate  $define_mod  which set up the tables described above so that the

use of standard predicates will cause the correct modules to be  loaded  in

the _$undefined_pred routine, and the correct names to be used.


10.  Macros




     SB-Prolog features a facility for the definition and expansion of mac-

ros  that is fully compatible with the runtime system.  Its basic mechanism

is a simple partial evaluator.  It is called by both consult  and  compile,

so  that macro expansion occurs independently of whether the code is inter-

preted  or  compiled  (but  not  when  asserted).   Moreover,   the   macro


                                    80












definitions av%retained as clauses at runtime, so that invocation of macros

via call/1 at runtime (or from asserted clauses) does not pose  a  problem.

This  means,  however,  that  if  the  same macro is used in many different

files, it will be loaded more than once,  thus  leading  to  wasetd  space.

This ought to be thought about and fixed.


     The source for the macro expander is  in  the  SB-Prolog  system  file

modlib/src/$mac.P.


10.1.  Defining Macros




     `Macros', or predicates to be evaluated at compile-time,  are  defined

by clauses of the form

            Head ::- Body


where facts have `true' as their body.  The partial evaluator  will  expand

any call to a predicate defined by ::-/2 that unifies with the head of only

one clause in ::-/2. If a call unifies with  the  head  of  more  than  one

clause  in  ::-/2, it will not be expanded Notice that this is not a funda-

mental restriction, since `;' is permitted in the body of  a  clause.   The

partial evaluator also converts each definition of the form

            Head ::- Body.


to a clause of the form

            Head :- Body.


and adds this second clause to the other ``normal'' clauses that were  read

from  the  file.   This  ensures  that  calls to the macro at runtime, e.g.


                                    81












through call/1 or from unexpanded calls in the program  do  not  cause  any

problems.


     The  partial  evaluator  is  actually  a  Prolog  interpreter  written

`purely'  in   Prolog,  i.e.,  variable assignments are explicitly handled.

This is necessary to be able to handle impure constructs such  as  `var(X),

X=a'.  As a result this is a very slow Prolog evaluator.


     Since naive partial evaluation can  go  into  an  infinite  loop,  SB-

Prolog's  partial  evaluator  maintains  a  depth-bound and will not expand

recursive calls deeper than that.  The depth is determined by the globalset

predicate  $mac_depth.  The default value for $mac_depth is 50  This can be

changed to some other value n by executing

            | ?- globalset($mac_depth(n)).



10.2.  Macro Expander Options




The following options are recognized by the macro expander:


d    Dumps all clauses to the user after expansion.  Useful for debugging.


e    Expand macros.  If omitted, the expander simply  converts  each  ::-/2

     clause to a normal :-/2 clause.


v    ``Verbose'' mode.  Prints macros that are/are not being expanded.








                                    82












11.  Extension Tables




     Extension tables store the calls and answers for  a  predicate.  If  a

call  has  been made before, answers are retrieved from the extension table

instead of being recomputed. Extension tables provide a  caching  mechanism

for  Prolog.  In  addition, extension tables affect the termination charac-

teristics of recursive programs. Some Prolog programs, which are  logically

correct,  enter  an infinite loop due to recursive predicates. An extension

table saved on recursive predicates can find all answers (provided the  set

of  such answers is finite) and terminate for some logic programs for which

Prolog's evaluation strategy enters an infinite loop. Iterations  over  the

extension  table execution strategy provides complete evaluation of queries

over function-free Horn clause programs.


     To be able to use the simple extension table evaluation on  a  set  of

predicates,  the  source  file should either be consulted, or compiled with

the t option (the t option keeps the assembler from  optimizing  subroutine

linkage  and  allows  the  extension  table  facility to intercept calls to

predicates).


     To use extension table execution, all predicates that are to be  saved

in the extension table must be passed to et/1. For example,

            | ?- et([pred1/1, pred2/2]), et(pred3/2)


will set up ``ET-points'' for  the  for  predicates  pred1/1,  pred2/2  and

pred3/2, which will cause extension tables for these predicates to be main-

tained during execution. At the time of the call to et/1, these  predicates


                                    83












must be defined, either by having been loaded, or through consult.


     The predicate noet/1 takes a list of predicate/arity pairs  for  which

ET-points  should be deleted.  Notice that once an ET-point has been set up

for a predicate, it  will  be  maintained  unless  explicitly  deleted  via

noet/1.   If the definition of a predicate which has an ET-point defined is

to be updated, the ET-point must first be deleted via noet/1.   The  predi-

cate can then be reloaded and a new ET-point established.  This is enforced

by the failure of the goal ``et(P/N)'' if an ET-point  already  exists  for

the  argument predicate.  In this case, the following error message will be

displayed:

            *et* already defined for: P/N



     There are, in fact, two extension  table  algorithms:  a  simple  one,

which simply caches calls to predicates which have ET-points defined; and a

complete ET algorithm, which iterates the simple extension table  algorithm

until no more answers can be found.  The simple algorithm is more efficient

than the complete one; however, the simple algorithm is  not  complete  for

certain  especially  nasty  forms  of  mutual recursion, while the complete

algorithm is.  To use the simple extension table algorithm, predicates  can

simply  be  called as usual.  The complete extension table algorithm may be

used via the query

            | ?- et_star(Query).



The extension table algorithm is intended for predicates that are  ``essen-

tially  pure'',  and results are not guaranteed for code using impure code.



                                    84












The extension table algorithm  saves  only  those  answers  which  are  not

instances  of  what  is already in the table, and uses these answers if the

current call is an instance of a call already made.  For example, if a call

p(X,  Y), with X and Y uninstantiated, is encountered and inserted into the

extension table, then a subsequent call p(X, b) will be computed using  the

answers for p(X, Y) already in the extension table.  Notice that this might

not work if var/nonvar tests are used on the second argument in the evalua-

tion of p.


     Another problem with using impure code is that if an ET  predicate  is

cut  over,  then the saved call implies that all answers for that predicate

were computed, but there are only partial results in the ET because of  the

cut.   So  on  a subsequent call the incomplete extension table answers are

used when all answers are expected.

    Example:
            r(X,Y) :- p(X,Y),q(Y,Z),!,fail.
            | ?-  r(X,Y) ; p(X,Y).



Let p be an ET predicate whose  evaluation  yields  many  tuples.   In  the

evaluation  of  the  query,  r(X,Y)  makes a call to p(X,Y).  Assuming that

there is a tuple such that q(Y,Z) succeeds with the first p tuple then  the

evaluation  of  p  is  cut  over.  The call to p(X,Y) in the query uses the

extension table because of the previous call in the evaluation  of  r(X,Y).

Only  one  answer is found, whereas the relation p contains many tuples, so

the computation is not complete.  Note that "cuts" used within the  evalua-

tion  of an ET predicate are ok, as long as they don't cut over the evalua-

tion of another ET predicate. The evaluation of  the  predicate  that  uses



                                    85












cuts  does  not  cut  over any et processing (such as storing or retrieving

answers) so that the tuples that are computed are saved. In  the  following

example,  the ET is used to generate prime numbers where an ET point is put

on prime/1.

    Example:

    prime(I) :- globalset(globalgenint(2)),fail.                    /* Generating Primes */
    prime(I) :- genint(I), not(div(I)).
    div(I) :- prime(X), 0 is I mod X.

    genint(N) :-
        repeat,
            globalgenint(N),
            N1 is N+1,
            globalset(globalgenint(N1)).



The following summarizes the library predicates  supporting  the  extension

table facility:




et(L)


     Sets up an ET-point on the predicates L, which causes calls and anwers

     to  these  predicates  to  be  saved  in an ``extension table''.  L is

     either a term Pred/Arity, where Pred is a predicate symbol  and  Arity

     its  arity,  or  a set of such terms represented as a list.  L must be

     instantiated, and the predicates specified in it defined, at the  time

     of  the  call  to  et/1.  Gives error messages and fails if any of the

     predicates in L is undefined, or if an ET-point already exists on  any

     of  them; in this case, no ET-point is set up on any of the predicates

     in L.




                                    86












et_star(Goal)


     Invokes the complete extension table algorithm on the goal Goal.


et_points(L)


     Unifies L with a list of predicates for which an ET-point is  defined.

     L is the empty list [] if there are no ET-points defined.


noet(L)


     Deletes ET-points on the predicates specified in L.   L  is  either  a

     term P/N, where P is the name of a predicate and N its arity, or a set

     of such terms represented as a list.  Gives error messages  and  fails

     if  there  is  no  ET-point  on  any of the predicates specified in L.

     Deleting an ET-point for  a  predicate  also  removes  the  calls  and

     answers  stored in the extension table for that predicate.  The exten-

     sion tables for all predicates for which ET-points are defined may  be

     deleted using et_points/1 in cojnunction with noet/1.



     L must be instantiated at the time of the call to noet/1.


et_remove(L)


     Removes both calls and answers for the predicates specified in L.   In

     effect, this results in the extension table for these predicates to be

     set to empty.  L must be instantiated at  the  time  of  the  call  to

     either  a  term P/N, where P is a predicate with arity N, or a list of

     such terms.  An error occurs if any of the predicates in  L  does  not



                                    87












     have an ET-point set.



     All extension tables can be emptied by using et_points/1  in  conjunc-

     tion with et_remove/1.


et_answers(P/N, Term)


     Retrieves the answers stored in the extension table for the  predicate

     P/N  in  Term  one at a time.  Term is of the form P(t<1>, ..., t<N>).

     An error results and et_answers/2 fails if P/N is not fully  specified

     (ground), or if P/N does not have an ET-point set.


et_calls(P/N, Term)


     Retrieves the calls stored in the extension table  for  the  predicate

     P/N  in  Term  one at a time.  Term is of the form P(t<1>, ..., t<N>).

     An error results and et_calls/2 fails if P/N is  not  fully  specified

     (ground), or if P/N does not have an ET-point set.


12.  Profiling Programs




     SB-Prolog provides a utility  for  profiling  programs  interactively.

Two  kinds of profiling are supported: one may count the number of calls to

a predicate, or compute the time spent in a  predicate.   It  is  important

that  the  predicates being profiled are either consulted, or compiled with

the t option, so that calls to the relevant predicates can  be  intercepted

by the profiler.




                                    88












     To use the profiler, predicates whose calls are to be counted must  be

passed to count/1, e.g.

            | ?- count([p/1, q/2]), count(r/3).


will set up ``count-points'' on the predicates p/1, q/2  and  r/3.   Predi-

cates whose calls are to be timed have to be passed to time/1, e.g.

            | ?- time([s/1, t/2]), time(u/3).


will set up ``time-points'' on the predicates s/1, t/2 and u/3.  It is pos-

sible  to  set  both  count-points  and  time-points on the same predicate.

After count-points and time-points have been set, the program may  be  exe-

cuted  as  many times as desired: the profiling system will accumulate call

counts and execution times for the appropriate predicates.  Execution  pro-

files  may  be  obtained using the predicates prof_stats/0 or prof_stats/1.

Using prof_stats/0 to display the execution profile  will  cause  the  call

counts  and  execution  times of predicates being profiled to be reset to 0

(this may be avoided by using prof_stats/1).


     It should be noted that in this context, the ``execution time'' for  a

predicate  is  an  estimate  of  the total time spent in the subtrees below

calls to that predicate (including failed subtrees):  thus,  the  execution

time figures may be dilated slightly if the subtree below a timed predicate

contains predicates that are being profiled, because of the time taken  for

updating the call counts and execution times.  For each predicate, the exe-

cution time is displayed as the fraction of time spent, in  computation  in

subtrees  under  calls to that predicate, relative to the time elapsed from

the last time profiling was timed on or the last time profiling  statistics



                                    89












were taken, whichever was more recent.


     The following summarizes the library predicates supporting profiling:




count(L)


     Sets up a count-point on the predicates L, which causes calls to these

     predicates  to be counted, and turns profiling on.  L is either a term

     Pred/Arity, where Pred is a predicate symbol and Arity its arity, or a

     set  of such terms represented as a list.  L must be instantiated, and

     the predicates specified in it defined, at the time  of  the  call  to

     count/1.


time(L)


     Sets up a time-point on the predicates L, which causes execution times

     for  calls  to these predicates to be accumulated, and turns profiling

     on.  L is either a term Pred/Arity, where Pred is a  predicate  symbol

     and  Arity its arity, or a set of such terms represented as a list.  L

     must be instantiated, and the predicates specified in it  defined,  at

     the time of the call to time/1.


nocount(L)


     Deletes the count-point on the predicates  L.   L  is  either  a  term

     Pred/Arity, where Pred is a predicate symbol and Arity its arity, or a

     set of such terms represented as a list.  L must be instantiated,  and

     the  predicates  specified  in  it defined, at the time of the call to



                                    90












     nocount/1.


notime(L)


     Deletes the time-point on the  predicates  L.   L  is  either  a  term

     Pred/Arity, where Pred is a predicate symbol and Arity its arity, or a

     set of such terms represented as a list.  L must be instantiated,  and

     the  predicates  specified  in  it defined, at the time of the call to

     time/1.


profiling


     Displays information about whether profile mode  is  on  or  not,  and

     lists predicates that have count- and time-points set on them.


prof_reset(L)


     Resets call counts and/or execution times for the predicates L.  L  is

     either  a  term Pred/Arity, where Pred is a predicate symbol and Arity

     its arity, or a set of such terms represented as a list.   L  must  be

     instantiated,  and the predicates specified in it defined, at the time

     of the call to prof_reset/1.


resetcount(L)


     Resets call  counts  for  the  predicates  L.   L  is  either  a  term

     Pred/Arity, where Pred is a predicate symbol and Arity its arity, or a

     set of such terms represented as a list.  L must be instantiated,  and

     the  predicates  specified  in  it defined, at the time of the call to

     resetcount/1.


                                    91












resettime(L)


     Resets execution times for the predicates  L.   L  is  either  a  term

     Pred/Arity, where Pred is a predicate symbol and Arity its arity, or a

     set of such terms represented as a list.  L must be instantiated,  and

     the  predicates  specified  in  it defined, at the time of the call to

     resettime/1.


profile


     Turns profiling on.  This causes subsequent  execution  of  predicates

     with count- or time-points to be profiled, and is a no-op if there are

     no such predicates.  The predicates count/1 and time/1 cause profiling

     to be turned on automatically.


noprofile


     Turns profiling  off.   This  causes  count-  and  time-points  to  be

     ignored.


timepreds(L)


     Unifies L to a list of terms P/N where the predicate P of arity N  has

     a time point set on it.


countpreds(L)


     Unifies L to a list of terms P/N where the predicate P of arity N  has

     a count point set on it.





                                    92












prof_stats


     Causes the call counts and/or execution times  accumulated  since  the

     last  call  to  prof_stats/0 to be printed out for predicates that are

     being profiled.  The execution times are given  as  fractions  of  the

     total time elapsed since the last time profiling was turned on, or the

     last time prof_stats was called, whichever was most recent.  This also

     results  in  the  call  counts  and  relative execution times of these

     predicates being reset to 0.  Equivalent to prof_stats(1).


prof_stats(N)


     Causes the call counts and/or execution times  accumulated  since  the

     last  call  to  prof_stats/0 to be printed out for predicates that are

     being profiled.  The execution times are given  as  fractions  of  the

     total time elapsed since the last time profiling was turned on, or the

     last time prof_stats was called, whichever was most recent.  If  N  is

     1,  then  this  also results in the call counts and execution times of

     these predicates being reset to 0; otherwise, the call counts and exe-

     cution times are not reset.


13.  Other Library Utilities




     The SB-Prolog library contains various other utilities, some of  which

are listed below.


$append(X, Y, Z)




                                    93












     Succeeds if list Z is the concatenation of lists X and Y.


$member(X, L)


     Checks whether X unifies with any element of list L,  succeeding  more

     than once if there are multiple such elements.


$memberchk(X, L)


     Similar to $member/2, except that $memberchk/2 is deterministic,  i.e.

     does not succeed more than once for any call.


$reverse(L, R)


     Succeeds if R is the reverse of list L.  If L is not  a  fully  deter-

     mined  list,  i.e.  if the tail of L is a variable, this predicate can

     succeed arbitrarily many times.


$merge(X, Y, Z)


     Succeeds if Z is the list resulting from ``merging'' lists  X  and  Y,

     i.e. the elements of X together with any element of Y not occurring in

     X.  If X or Y contain duplicates, Z may also contain duplicates.


$absmember(X, L)


     Similar to $member/2, except that  it  checks  for  identity  (through

     ==/2) rather than unifiability (through =/2) of X with elements of L.


$nthmember(X, L, N)





                                    94












     Succeeds if the N[th.] element of the list L unifies with X.  Fails if

     N is greater than the length of L.  Either X and L, or L and N, should

     be instantiated at the time of the call.


$member2(X, L)


     Checks whether X unifies with any of the actual elements  of  L.   The

     only difference between this and $member/2 is on lists with a variable

     tail, e.g. [a, b, c | _ ]: while $member/2 would insert X at  the  end

     of  such  a  list  if  it  did not find it, $member2/2 only checks for

     membership but does not insert it into the list if it is not there.


length(L, N)


     Succeeds if the length of the list L is N.  This predicate  is  deter-

     ministic  if  L  is  instantiated to a list of definite length, but is

     nondeterministic if L is a variable or has a variable tail.


subsumes(X, Y) Succeeds if the term X subsumes the term Y (i.e. if Y is  an

instance of X).


14.  Pragma Files




     Users may specify pragma information about  SB-Prolog  programs  in  a

file called the pragma file for the program.  The pragma file corresponding

to a Prolog source file foo is a file foo.def which is either in  the  same

directory as the source file, or is in a subdirectory defs in the directory

containing the source file.  In other  words,  relative  to  the  directory



                                    95












containing  the  source  file foo, the pragma file can be either foo.def or

defs/foo.def.


     Pragma information in such a file is  specified  as  a  set  of  facts

prag/3.   The  first  and  second arguments are, respectively, the name and

arity of the predicate for which information is being specified.  The third

argument is the pragma being specified, and can be either a term, or a list

of terms.  Thus, for example, to specify that an index is to be created  on

the first argument position for a predicate bar/3 in the file foo, we would

enter, in a file foo.def, the fact ``prag(bar, 3, index)''  or  ``prag(bar,

3, [index])''.


     The pragma information that may  be  specified  is  limited,  at  this

point,  to  information  about  indexing.   If an index is to be created on

argument n of a predicate, the corresponding pragma is a term ``index(n)''.

In the special case where n = 1, the pragma ``index(1)'' may be abbreviated

to ``index''.




Acknowledgements


     A large number of people were involved, at some time or another,  with

the  Logic  Programming group at SUNY, Stony Brook, and  deserve credit for

bringing the SB-Prolog system to its present form.  The following names, in

particular,  ought  to  be  mentioned:  David  Scott  Warren, Weidong Chen,

Suzanne Dietrich, Sanjay Manchanda, Jiyang Xu  and  David  Znidarsic.   The

author  is also grateful to Fernando Pereira for permission to use material

from the C-Prolog manual for the descriptions of Prolog syntax and many  of


                                    96












the builtins.




















































                                    97












Appendix 1: Evaluable Predicates of SB-Prolog






     An entry of ``B'' indicates  a  builtin  predicate,  ``I''  an  inline

predicate,  and  ``L''  a  library  predicate.   A ``P'' indicates that the

predicate is handled by the preprocessor during compilation and/or consult-

ing.


(L)     _$undefined_pred/1....    6    (I)     =\=/2 ................   32
(L)     compile/1 ............    7    (I)     </2 ..................   33
(L)     compile/2 ............    7    (I)     >/2 ..................   33
(L)     compile/3 ............    7    (I)     =</2 .................   33
(L)     compile/4 ............    7    (I)     >=/2 .................   33
(B)     load/1 ...............    8    (B)     floor/2 ..............   33
(L)     consult/1 ............    9    (B)     floatc/3 .............   34
(L)     consult/2 ............    9    (B)     exp/2 ................   34
(P)     :-/1 .................   11    (B)     square/2 .............   34
(L)     op/3 .................   18    (B)     sin/2 ................   34
(B)     see/1 ................   26    (I)     `,'/2 ................   35
(B)     seen .................   26    (I)     `;'/2 ................   35
(B)     tell/1 ...............   26    (I)     true/0 ...............   35
(B)     telling/1 ............   26    (I)     =/2 ..................   35
(B)     told/0 ...............   26    (P)     !/0 ..................   35
(B)     $exists/1 ............   26    (P)     not/1 ................   36
(L)     read/1 ...............   27    (P)     ->/2 .................   36
(L)     write/1 ..............   27    (L)     repeat/0 .............   36
(L)     display/1 ............   27    (I)     fail/0 ...............   36
(L)     writeq/1 .............   27    (I)     var/1 ................   36
(L)     print/1 ..............   27    (I)     nonvar/1 .............   37
(B)     writename/1 ..........   27    (B)     atom/1 ...............   37
(B)     writeqname/1 .........   28    (B)     integer/1. ...........   37
(L)     print_al/2 ...........   28    (B)     real/1 ...............   37
(L)     print_ar/2 ...........   28    (B)     number/1 .............   37
(B)     nl/0 .................   28    (B)     atomic/1 .............   37
(B)     get0/1 ...............   28    (B)     structure/1 ..........   37
(B)     get/1 ................   29    (L)     functor/3 ............   38
(B)     put/1 ................   29    (B)     arg/3 ................   38
(B)     tab/1 ................   29    (L)     =../2 ................   38
(I)     is/2 .................   31    (B)     name/2 ...............   39
(L)     eval/2 ...............   32    (P)     call/1 ...............   39
(I)     =:=/2 ................   32    (B)     conlength/2 ..........   40




                                    98











(L)     setof/3 ..............   40    (B)     system/1 .............   59
(L)     bagof/3 ..............   41    (B)     syscall/3 ............   59
(B)     ==/2 .................   43    (L)     globalset/1 ..........   61
(B)     \==/2 ................   43    (L)     gennum/1 .............   61
(B)     @</2 .................   43    (L)     gensym/2 .............   61
(B)     @>/2 .................   43    (L)     trace/1 ..............   62
(B)     @=</2 ................   43    (L)     untrace/1 ............   65
(B)     @>=/2 ................   44    (L)     spy/1 ................   65
(B)     compare/3 ............   44    (L)     nospy/1 ..............   65
(L)     sort/2 ...............   44    (L)     debug/0 ..............   65
(L)     alloc_perm/2 .........   45    (L)     nodebug/0 ............   65
(L)     alloc_heap/2 .........   46    (L)     debugging/0 ..........   66
(L)     $alloc_heap/5 ........   46    (L)     tracepreds/1 .........   66
(L)     trimbuff/3 ...........   46    (L)     spypreds/1 ...........   66
(L)     $trim_buff/4 .........   47    (L)     trace/0 ..............   66
(L)     assert/1 .............   49    (L)     untrace/0 ............   66
(L)     assert/2 .............   49    (P)     ::-/2 ................   81
(L)     asserti/2 ............   50    (L)     et/1 .................   86
(L)     asserta/1 ............   50    (L)     et_star/1 ............   87
(L)     asserta/2 ............   50    (L)     et_points/1 ..........   87
(L)     assertz/1 ............   50    (L)     noet/1 ...............   87
(L)     assertz/2 ............   50    (L)     et_remove/1 ..........   88
(L)     assert_union/2 .......   51    (L)     et_calls/2 ...........   88
(L)     $assert/4 ............   51    (L)     count/1 ..............   90
(L)     $assertf_alloc_t .....   52    (L)     time/1 ...............   90
(L)     retract/1 ............   52    (L)     nocount/1 ............   90
(L)     abolish/1 ............   53    (L)     notime/1 .............   91
(L)     abolish/2 ............   53    (L)     profiling/0 ..........   91
(L)     call_ref/2 ...........   53    (L)     prof_reset/1 .........   91
(L)     call_ref/3 ...........   53    (L)     resetcount/1 .........   91
(L)     $db_new_prref/3 ......   54    (L)     resettime/1 ..........   92
(L)     $db_assert_fact/5 ....   54    (L)     profile/0 ............   92
(L)     $db_add_clref/7 ......   55    (L)     noprofile/0 ..........   92
(L)     $db_call_prref/2 .....   55    (L)     timepreds/1 ..........   92
(L)     $db_call_prref_s/2 ...   55    (L)     countpreds/1 .........   92
(L)     $db_get_clauses/3 ....   56    (L)     prof_stats/0 .........   93
(L)     $db_kill_clause/1 ....   56    (L)     prof_stats/1 .........   93
(L)     break/0 ..............   57    (L)     $append/3 ............   94
(B)     abort/0 ..............   57    (L)     $member/2 ............   94
(B)     save/1 ...............   57    (L)     $reverse/2 ...........   94
(B)     restore/1 ............   57    (L)     $merge/3 .............   94
(B)     cputime/1 ............   58    (L)     $absmember/2 .........   94
(L)     $getenv/2 ............   58    (L)     $nthmember/3 .........   95
(B)     statistics/0 .........   58    (L)     length/2 .............   95
(L)     nodynload/2 ..........   58    (L)     subsumes/2 ...........   95
(B)     symtype/2 ............   59








                                    99












Appendix 2: Adding Builtins to SB-Prolog




     Adding a builtin involves writing the C code for the desired case  and

installing  it  into  the simulator.  The files in the irectory sim/builtin

contain the C code for the builtin predicates supported by the system.  The

following procedure is to be followed when adding a builtin to the system:




I. Installing C Code:


(1)  Go to the directory sim/builtin.


(2)  Look at the #defines in the file builtin.h, and  choose  a  number  N1

     (between  0  and 255) which is not in use to be the builtin number for

     the new builtin.


(3)  Add to the file builtin.h the line

                 #define NEWBUILTIN N1



(4)  The convention is that the code for builtin will be in a parameterless

     procedure  named  b_NEWBUILTIN.   Modify the file init_branch.c in the

     directory sim/builtin by adding these lines:

                 extern int b_NEWBUILTIN();
         and
                 set_b_inst ( NEWBUILTIN, b_NEWBUILTIN );


     in the appropriate places.






                                    100












(5)  The builtins are compiled together  into  one  object  file,  builtin.

     Update  the  file  Makefile  by appending the name of your object code

     file at the end of the line ``OBJS = ... '' and insert the appropriate

     commands to compile your C source file, e.g.:

         OBJS = [ ... other file names ... ] newbuiltin.o

          ...

         newbuiltin.o: $(HS)
                 cc $(CFLAGS) newbuiltin.c



(6)  Execute the updated make file to create an updated object  file  buil-

     tin.


(7)  Go to the directory sim and execute make to install the new file buil-

     tin.




II. Installing Prolog Code:


     Assume that the builtin predicate to be added  is  newbuiltin/4.   The

procedure for installing the Prolog code for this is as follows:


(1)  Go to the SB-Prolog system directory lib/src, where the Prolog  source

     for the library routines is kept.


(2)  Each builtin definition is of the form



                 pred( ... ) :- '_$builtin'(N).






                                    101












     where N is an integer, the builtin number of pred.


(3)  Create a Prolog source file newbuiltin.P (notice  correspondence  with

     the name of the predicate being defined) containing the definition



                 newbuiltin(A,B,C,D) :- '_$builtin'(N1).




     where N1 is the builtin number of the predicate  newbuiltin,  obtained

     when installing the C code for the builtin (see above).


(4)  Compile this Prolog predicate, using the  simulator  and  the  compile

     predicate, into a file newbuiltin (notice correspondence with the name

     of the predicate being defined) in the SB-Prolog directory lib.





























                                    102












                               TABLE OF CONTENTS


       1 :  Introduction .............................................    1
       2 :  Getting Started ..........................................    3
         2.1 :  The Dynamic Loader Search Path .......................    3
         2.2 :  System Directories ...................................    5
         2.3 :  Invoking the Simulator ...............................    5
         2.4 :  Executing Programs ...................................    7
            2.4.1 :  Compiling Programs ..............................    7
            2.4.2 :  Loading Byte Code Files .........................    8
            2.4.3 :  Consulting Programs .............................    9
         2.5 :  Execution Directives .................................   11
       3 :  Syntax ...................................................   12
         3.1 :  Terms ................................................   12
         3.2 :  Operators ............................................   16
       4 :  SB-Prolog: Operational Semantics .........................   20
         4.1 :  Standard Execution Behaviour .........................   20
         4.2 :  Cuts and If-Then-Else ................................   21
         4.3 :  Unification of Floating Point Numbers ................   22
       5 :  Evaluable Predicates .....................................   24
         5.1 :  Input and Output .....................................   25
            5.1.1 :  File Handling ...................................   26
            5.1.2 :  Term I/O ........................................   27
            5.1.3 :  Character I/O ...................................   28
         5.2 :  Arithmetic ...........................................   29
         5.3 :  Convenience ..........................................   35
         5.4 :  Extra Control ........................................   35
         5.5 :  Meta-Logical .........................................   36
         5.6 :  Sets .................................................   40
         5.7 :  Comparison of Terms ..................................   42
         5.8 :  Buffers ..............................................   44
         5.9 :  Modification of the Program ..........................   47
         5.10 :  Environmental .......................................   56
         5.11 :  Global Values .......................................   60
       6 :  Debugging ................................................   62
         6.1 :  High Level Tracing ...................................   62
         6.2 :  Low Level Tracing ....................................   66
       7 :  The Simulator ............................................   67
         7.1 :  Invoking the Simulator ...............................   67
         7.2 :  Simulator Options ....................................   68
         7.3 :  Interrupt Handling ...................................   70
       8 :  The Compiler .............................................   70
         8.1 :  Structure of the Compiler ............................   71
         8.2 :  Invoking the Compiler ................................   71
         8.3 :  Compiler Options .....................................   73
         8.4 :  A Note on Coding for Efficiency ......................   74
            8.4.1 :  Avoiding Creation of Backtrack Points ...........   74
            8.4.2 :  Minimizing Data Movement Between Registers ......   77
         8.5 :  Assembly .............................................   77















       9 :  Modules ..................................................   78
       10 :  Macros ..................................................   80
         10.1 :  Defining Macros .....................................   81
         10.2 :  Macro Expander Options ..............................   82
       11 :  Extension Tables ........................................   83
       12 :  Profiling Programs ......................................   88
       13 :  Other Library Utilities .................................   93
       14 :  Pragma Files ............................................   95

     Appendix 1: Evaluable Predicates of SB-Prolog ...................   98

     Appendix 2: Adding Builtins to SB-Prolog ........................  100